Home > Theory Of Computation

### Regular Expression Examples

Regular Expression Examples   Describe The Following Sets Of Regular Expressions {0,1,2}  {∧,ab} {abb,a,b} {∧,0,00,000....} {1,11,111,1111,......} How To Form Regular Expressions From Above Sets??   1.{0,1,2} This Is The Set Given Containing Symbols 0,1,2 That Means It Could Contain 0 Or 1 Or 2 These Are Symbols Contained In The Set.   In Regular Expression, It Can Be Written Like This R=0+1+2

### Regular Expression s

Regular Expression s Are Used For Representing  Certain Sets Of Strings In A Algebraic Function.   Rules 1) Any Terminal Symbol i.e Symbols ε, Σ Including ∧(Empty) And Φ(Phi) Are Regular Expresions. Example:- Input Symbols Like a,b,1,0,∧,Φ Are Regular Expresions   2) The Union Of Two Regular Expresions Is Also A Regular Expresion. Example-R1,R2 (R1,R2) Is A Regular Expresion.   3) The Concatenation Of Two

### Conversion Of E-NFA To DFA

Conversion Of E-NFA To DFA Example:- ε-Closure (q0) --> {q0,q1} q01 = [q0q1]

### Conversion Of E-NFA To DFA

Conversion Of E-NFA To DFA Let M=(Q,Σ,δ,q0,F) Be The NFA M1=(Q1,Σ,δ1,q01,F1) Be The Equivalent DFA   1) Initial State:-  q01 - ε-Closure(q0) 2) Construction Of δ1 δ1(q,x)=ε-Closure(δ(q,x)) Start The Construction Of δ1 With Initial State And Continue For Every New State. 3) Final State:- Every Subset Which Contain The Final State Of ε-NFA Is Final State Of DFA   Example:- 1)  Initial State:- q01=ε-Closure(q0) ={q0,q1} q0=q0,q1 2) DFA

### Conversion Of E-NFA To NFA – Theory Of Computation

Conversion Of E-NFA To NFA - Theory Of Computation Example-1 ε-Closure (q0) - {q0,q1} ε-Closure (q1) - {q1} ε-Closure (q2) - {q2} ε-Closure (q3) - {q3,q1q2} 1)  Initial State - q0 2) Construction Of δ1 Note:- When We Convert ε-NFA To NFA, There Will Be No Change In Number Of States. This Is The Resultant Diagram. There Is No-Transition With 'ε"(Epsilon)

### Conversion Of E-NFA To NFA – Finite Automata –

Conversion Of E-NFA To NFA - Finite Automata The Process Of Conversion Of ε-NFA To NFA Is Called As Thomson Construction. Note:- No Change In Initial State No Change In The Total No. Of States May Be Change In Final States Algorithm Let M=(Q,Σ,δ,q0,F) - ε-NFA M1= (Q1,Σ,δ1,q01,F1) - NFA 1) Initial State q01=q0 2) Construction Of δ1 δ1 (q,x)=ε-Closure(δ(ε-Closure(q),x) 3) Final State Every State Who's ε-Closure

### E-closure – Theory Of Computation Pdf

E-closure - Theory Of Computation Pdf - ε-Closure - If 'q' Is Any State In ε-NFA Set Of All The State Which Are At '0' Distance From State 'q' Is Called As Closure Of (q) (or) The Set Of All The State That Can Reach From State 'q' Of ε Is Called As ε-Closure Of

### NFA With ε-Moves Or ε-NFA

NFA With ε-Moves Or ε-NFA The NFA Which Has Transition Even For Empty String ε Is The Called An ε-nfa ε-NFA Has 5-Tuple M=(Q,Σ,δ,q0,F) Where Q=Set Of States Σ=I/p Alphabets δ=Transition Function(Q×Σ∪{ε}--> 2Q) q0=Initial State F= Final State Q×Σ--> Q--> DFA Q×Σ--> 2Q-->NFA Q×Σ∪{ε}--> 2Q--> ε-NFA   Example L={am,bm/m,n≥0} L={a,b,ε,ab,abb...} 2.L={anbUbna/n≥0} 3.L={(ab)n/n≥0}