Construct minimal DFA which accepts set of all strings over ∑={a,b} in which every ‘a’ should never be followed by ‘bb’.

SOLUTION:

∑={a,b}

L = {∈,b, bb, bbb,………,a, aa, aaa, ……., ab, aab, baab, ………. }

Ø  So DFA can be Q={ q₀ , q₁ , q₂},∑={a,b}, q₀={ q₀},F={q₂} and δ is given by the table

1)Transition diagram:

2)Transition Table:

Present State	Next State
	Input a	Input b
à *q0	q1	q0
* q1	q1	q2
*q2	q1	D
D	D	D

  3)Transition function:

δ( q₀, a)= q₁     ,δ (q₀,b)= q₀

            δ( q₁, a)= q₁     ,δ (q₁,b)= q₂   

δ( q₂, a)= q₁     ,δ (q₂,b)= D

δ( D, a)= D      ,δ (D, b)= D