Home > Theory Of Computation > DFA Example : Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb

DFA Example : Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb

Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb

Condition Given Is

The String Must End With aa Or Can End End With bb.

L={aa,bb,aaa,bbb,abaa,babb} // Infinite String

 

Lets’s Create NFA (Smallest String Is ‘aa’ Or ‘bb’)

DFA

Remember

  • Dead State Concept Will Not Comes In The ‘End With ‘ Problems.
  • If I Get ‘a’ Of ‘q2‘, I’ll Put Self Loop Because, It Doesn’t Matter If I Get Any Number Of a’s After q1(a), I’m Ending With ‘aa’ That’s It.
  • If I Get ‘b’ On ‘q4‘ I’ll Put Self Loop Because It Doesn’t Matter If I Get Any Number Of b’s After ‘q3‘(b), I’m Ending bb, That’s It.
  • If I Get ‘b’ On My Final State ‘q2‘, ill Send To ‘q3‘ (Non-Final State) So That It End’s ‘bb’
  • If I Get ‘a’ On My Final State ‘q4‘ I’ll Send It To ‘q1‘, So That It Ends With ‘aa’.
  • In This Case, I Can’t Merge Both The Final States ‘q2‘ and ‘q4‘ Because Final States Are Different For Both The Two Possible Strings.

 

2 thoughts on “DFA Example : Construct Minimal Deterministic Finite Automata Ends With aa Or Ends With bb

Leave a Reply