start1 ab 4 5 a b Figure 2 SolutionFigure 2 Regular Expressi

Solution

Figure 2
Regular Expression accepted by language

(a+ab)

Q - Set of States 1,2,3,4,5
Set of symbols - a,b
Transition rules:
Present State    Next State for input a Next State for input b
1                      4                       2
2                      3                       5
3                      5                       5
4                      5                       4
5                      5                       5

1 - Initial state

Final state - 4,3

Figure 4
Regular Expression accepted by language

(0{1}*0{0,1}*+ 1{0}*(0+1){0,1}*)

Q - Set of States q0,q1,q2,q3,q4
Set of symbols - 0,1
Transition rules:
Present State    Next State for input 0 Next State for input 1
q0                     q3                     q1
q1                     q1,q2                  q2
q2                      q2                    q2
q3                     q4                     q3
q4                     q4                     q4

q0 - Initial state

Final state - q4,q2