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}$