Home > dfa and nfa

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 Problem

NFA Problem - Consider The NFA M Given Below. Let 'M' Be The NFA Obtain From By Interchanging Final And Non- Final States. Let L And L1 Be The Language Accepted By M And M1 Respectively Then Which Of The Following Statement Is True. L=L1 L⊆L1 L1⊆L L∩L1=Φ L∩L1=Σ* L∪L1=Φ L∪L1=Σ* Solution:- Given NFA 'M' Is He

Read More

Conversion Of NFA To DFA

Conversion Of NFA To DFA Construct The DFA For The Following NFA Solution:- DFA TRANSITION TABLE AFTER MERGING SAME STATES TO ONE STATE, I'LL DELETE ONE OF THESE STATES If You Observe Given NFA The String Is Containing ab As Substring. In This D FA Also The String Contains ab As Substring.   Every State In This Given

Read More

NFA Example: Construct The NFA That Accepts All The String Of a & b Where No. Of a Are Exactly 2

Construct The NFA That Accepts All The String Of a & b Where No. Of a (i) Exactly 2 (ii) At Least 2 (iii) At-Most 2 (iv) ≅ 0(Mod 3) (v)  ≅ 1(Mod 5) (vi)  ≅ 0(Mod 2) (vii)  ≅ 1(Mod 2)   (i) Exactly 2 Σ=[a,b} L={aa,....} (ii) At Least 2   (iii) At-Most 2 (Not More Than 2) (iv) ≅ 0(Mod 3) (v)  ≅ 1(Mod 5) (vi)  ≅ 0(Mod 2) (vii)  ≅ 1(Mod 2)  

Read More

NFA Example : Construct The NFA That Accepts All The Strings Of a & b Where Starts With aa Or bb

Construct The NFA That Accepts All The Strings Of a & b Where (i) Starts With aa Or bb (ii) End With aa Or bb (iii) Start With aa And End With bb Or Start With bb & End With aa   (i) Starts With aa Or bb L={aa or bb} NFA Transition Table (ii) End With aa Or bb L={......aa or

Read More

NFA Example : Construct The NFA That Accepts All The Strings Of 0 & 1 Where Every String Start And End With 0

Construct The NFA That Accepts All The Strings Of 0 & 1 (i) Where Every String Start And End With 0 (ii) Every String Start & End With Same Symbol (iii) Every String Start & End With Different Symbol   (i) Where Every String Start And End With 0 L={0,00,010,0110,01010....}   (ii) Every String Start & End With

Read More

NFA: Introduction About Non-Deterministic Finite Automata(NFA)

Introduction About Non-Deterministic Finite Automata(NFA) - Non-Deterministic Finite Automata Is A Incomplete System. The Non-Deterministic Finite Automata Which Has Zero, One Or More Than One Transition From Any State For Any Input Symbol Is Called Non-Deterministic Automata.   Non-Deterministic Finite Automata Is 5 Tuple Machine.   M={Q.Σ,δ,q0,F} Q-Set Of States Σ-Set Of Input Alphabets δ-Transition Function Q×Σ-2Q q0-Initial State F-

Read More

DFA Example : Consider he Following DFA And Count The Number Of All The String Accepted By DFA Which Have Length 5

Consider The Following DFA And Count The Number Of All The String Accepted By DFA Which Have Length 5   a) 29 b) 64 c) 26 d) 21 First Path Is You Have To See How Many Paths We Have To Reach Final State From Starting State. 15+7+4=26 Strings Are Possible.  

Read More

DFA Example : Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First,Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is

Consider Following DFA M, Let S Be The Set Of All 7 Bit String In Which First, Fourth And Last Bit Is One Then No. Of String In S Which Is Accepted By Machine M Is a) 15   b) 16   c) 7   d) 8   Solution:-  Given First, Fourth, Last Bit Is '0' Then No.

Read More