Construct a transition system which can accept strings over the alphabet a,b,……,z containing either cat or rat.

SOLUTION:

∑={a,b}

L =  {cat, rat, acat, bcat, arat, brat,……….. }

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

1)Transition diagram:

   2)Transition Table:

Present State	Next State
	c	a	t	r	b, d,…,q,s,u,..,z
à q0	q1	q0	q0	q1	q0
q1	q2	q2	q0	q1	q0
q2	q0	q0	q3	q0	q0
* q3	q3	q3	q3	q3	q3

  3)Transition function:

δ( q₀, c)= q₁     ,δ (q₀,a)= q₀     ,δ( q₀, t)= q₀    ,δ (q₀,r)= q₁    

            δ( q₁, c)= q₂     ,δ (q₁,a)= q₂     ,δ( q₁, t)= q₀    ,δ (q₁,r)= q₁

δ( q₂, c)= q₀     ,δ (q₂,a)= q₀     ,δ( q₂, t)= q₃    ,δ (q₂,r)= q₀

δ( q₃, c)= q₃     ,δ (q₂,a)= q_{3        ,}δ( q₃, t)= q₃   ,δ (q₂,r)= q₃

δ{ q₀,(b,d,…,q,s,u,…,z)}= q₀

δ{ q₁,(b,d,…,q,s,u,…,z)}= q₀

δ{ q₂,(b,d,…,q,s,u,…,z)}= q₀

δ{ q₃,(b,d,…,q,s,u,…,z)}= q₃