FOR FREE MATERIALS

Example:

Q = {${\mathit{q}}_{\mathbf{0}}\mathbf{ }\mathbf{,}\mathbf{ }{\mathit{q}}_{\mathbf{1}}$} ∑ = {a,b} ${\mathit{q}}_{\mathbf{1}}$ is the final state and ${\mathit{q}}_{\mathbf{0}}$ is the initial state 

Q X ∑ = {($q_0$, a), ($q_0$, b), ($q_1$, a), ($q_1$, b) }

Example:

∑ = {a,b}

It is not DFA because has no all moves i.e. ${\mathit{q}}_{\mathbf{0}}$ has no move for ‘a’ (input). As per the machine design if ‘a’ input move is not possible for ${\mathit{q}}_{\mathbf{0}}$ state then create a trap state to make a move for that state.

If there are no real states (move) for any alphabet (input) in that case create a trap state to make a  move for that state. Because in DFA all inputs move must be present for every state. Trap state is never part of the machine.

Language of the above machine:

L(M) = {b, ba, ba*, bbb, …. baabb,  baaaa….}

i.e. L(M) = {All strings started with symbol b and having odd number of b’s}

DFA has no infinite capacity storage, finite memory in form of state.

If we take        

                        2 states – 1bit

                        4 states – 2bit

                       $2^n$ states – n bit

So, if the bit is finite then definitely the number of states is also finite.

Example:

 Identify this machine is DFA or not.  ∑ = {a, b}

Language of the above machine M:

L = {a, ab, abbb, abbbb, ….} here L is followed by b

Find the correct language of above DFA?

1.$L_1$ = abb*

2.$L_2$ = ab*

3.$L_3$ = (a + b)* = Σ* where b* = {λ, b, bb, bbb, bbbb ….} 

Answer: 

Option 1: $L_1$= {ab, abb, abbb, abbbb….} all strings which accepted by the machine but one string a which accept by the above machine but never in $L_1$. So, $L_1$ is not a Language of M. {a ∊ ω, a ∉ $L_1$} $L_1$ ⊂ L(M) which fails the second condition of accepting L.

Option 2: (a + b)* = Σ*  it is not L(M) because it fails first condition of acceptation L

i.e. 

Option 3: Actually (a + b)* means all string generated by ‘a’ and ‘b’ i.e. universal set of strings generated by ‘a’ and ‘b’.

$L_2$ = ab*

$L_2$ = {ab, abb, abbb, abbbb….} here two condition are true so, L(M) = $L_2$

So, option 2 is correct answer.

Example:

∑ = {a, b}   

Language of the above machine: L(M) = (a+b)*