Minimized DFA no of states || Peter Linz

Question

$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$

Minimal DFA for the above language ?

Comments

@saurabh rai   how did you constructed ? from NFA to DFA or directly ?

use this to draw http://madebyevan.com/fsm/

---

debashish wt i did i construct two different dfa and than i take union of two dfa might i have made some extra state during its construction . but your approach is much better than my approach

---

I understand you joined then using epsilon, and then minimized using table. rt ?

Answer 1

Two DFA's are shown for languages {aⁿb | n>=0} and {bⁿa | n>=1} respectively .

Take these 2 as M1 and M2 respectively .

DFA M using cross product of M1×M2 having start state as {x1,y1} and mark final state as any state contain x2 or y3 and then do minimization .

The table is as follows => ( Sorry, for the handwriting )

Hence, after minimizing it, there are total 6 states and 2 final states . 

Required M will be =>

Answer 2

 

Min no of states = 6.

Comments

OK ! also share how ? I mean basic procedure directly or from NFA -> DFA ?

---

Or combined like Union of two MOD's ?

---

Directly.  

FIrst accept all smaller length strings -

here- b, ba, ab ...

And now think about patten...

like - aⁿb , bⁿa...

while solving this, I also did many mistakes and then finally got the exact solution...

Incase of DFA always think of removing redundancy... just keep practicing ..

---

Thanks ! .. accepting the min first. and reuse states I understand . but But I dont know why not coming ! ya needs practice !

---

@vijaycs,

Making table and taking union of both is very easy and faster , it will save a lot of time :)

---

@Kapilp,

Yes, may be ... but, I have not used that method yet and even I don't know that :p .

Can you please share any such solution.  ?

---

I replicated my exact procedure below ! @vijaycs and @saurav please verify any intermediate wrong conclusion if I have done !

L = $\\ \text{regex} = a^{*}b + bb^*a \\ \\ = (\epsilon +aa^*)b+bb^*a\\ \\ = b + aa^*b+bb^*a\\$

• Started with accepting the minimum string 'b' of L

• filling arrows at q1 now,

On 'a' form q1 we can not loop at q1. q2 is created. q2 becomes ending with 'a' state.

• still completing arrows at q1

On reading 'b' from q1 we can not loop at q1, because then $b^n$ will be accepted.

• Completing arrows at q3 now.

 Yes we can loop  at q3 on reading 'b'.

• Still Completing arrows at q3.

 On reading 'a' from q3 send it to ending with a state q2. Btw one more edge has been added on q0. On 'a' from q0 none of the existing states can be reused. So q4 is created.

• Completing arrows on q4 now.

 Reused q4 on reading 'a' and create new state q5 for 'b'. Mark q5 it as final and call it as ending with b state.

• Trap state is added from q2 and q5.

• Now I observe for final states that can be merged to a single states.I found q2 and q5 are doing the same thing on similar inputs and going to the same type ( or class ) of state (T)

---

@kapil: taking union means ? did you mean ? like product automata, and at the last step while selecting the final states, we need to make those compound states as final where ever (in compound states) initial dfa's final states exits ?

---

Great going @Debashish , (y)

Very nice explanation ... you have mentioned almost every point.

---

@vijaycs @Debashish , you can check my answer .

---

Q3 state is extra here.you can simply add loop to q1.hence humber of states is 5.

---

@sabrina if we remove $Q_{3}$, then DFA will accept $b^{n}$ which it should not

---

@Sabrina Kaur Dhalla

then it will accept strings like bb , bbb , bbbb which are not in language

Answer 3

$L=\left \{ a^{n}b\, n\geq 0 \right \}\, \cup \left \{ b^{n}a\, ,n\geqslant 1 \right \}$

$L=\left \{ b,ba,ab,bba,aab,bbba,aaab\cdots \right \}$

Here is my DFA-:

Note -:you have to make a  Trap(Dead State) for language $ba\left ( a+b \right )^{+} \, OR \,\, ab\left ( a+b \right )^{+}$

Answer 4

first draw epsilon nfa----

convert it into nfa without epsilon(A ia initial state)

after that convert it into dfa and minimize it so now it has total 6(2 final states) states
in dfa state O represents dead state