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

Read More

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

Read More

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  

Read More

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)

Read More

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

Read More

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

Read More

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}

Read More

NFA Example: Consider The NFA M Given Below

Consider The NFA M Given Below Let 'M' Be The NFA Obtain From M By Converting All The Non-Final States Into Final States If L & L1 Be The Language Accepted  By M And M1 Then Which Of The Following Statement Is Correct. a) L=L1 b) L⊂L1 c) L1⊂L d) L∩L1=Φ e) L∪L1=Σ* f) None   Before Solving This Problem I'll Tell Yo

Read More

NFA To DFA Conversion In Theory Of Computation

NFA To DFA Conversion In Theory Of Computation Construct The DFA For The Following NFA     DFA Using DFA Transition Table If All States Are Final The Minimal DFA Will Be My Initial State Will Be My Final State And This Is The DFA.   Example-2 Conversion Of NFA To DFA Find The Minimal No Of States In NFA Solution:- Transition

Read More