Question

Problem 24.3. Describe in words the language accepted by each automaton, and also give a regular expression.

Answer 1

apply arden's method:

q_o=q_o 0+q₂ 0+  ε

q₁=q₁ 0+q₀ 1

q₂=q₂ 0+q₁1

q0 regular expression is (q₂ 0+  ε)0*------------->1

q1 regular expression is q₀ 1 0*---------------->2

substitute 1 in 2 then

q1 becomes (q₂ 0+  ε)0*10*------->3

substitue 3 in q2 then

q₂=q₂ 0+q₁1

q2=q₂0+(q₂ 0+  ε)0*10*

=q₂₍0+ 00*10*)+  0*10*

regular expression for q2 is  0*10*(0+ 00*10*)*

substitue q2 regular expressin in qo then

q_o=q_o 0+0*10*(0+ 00*10*)*0+  ε

q0 regular expresiion is (0*10*(0+ 00*10*)*0+  ε)0*

substitue q0 regular expression in q1 then

q₁=q₁ 0+((0*10*(0+ 00*10*)*0+  ε)0*) 1

q1 regular expression is (((0*10*(0+ 00*10*)*0+  ε)0*) 1)0*

finally the regular expression is union of q1 and q2=(((0*10*(0+ 00*10*)*0+  ε)0*) 1)0*+ 0*10*(0+ 00*10*)*