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

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