Construct minimal DFA over ∑={a,b} which accepts L={a power n and b power n | n, m>=0}
SOLUTION:
∑={a,b}
L =
{∈, a, aa, aaa, ……., b, bb, bbb,………,ab,
aab, baab, ………. }
Ø So DFA can be Q={ q0 , q1 },∑={a,b}, q0={ q0},F={q1} and δ is given by the table
1)Transition
diagram:
2)Transition Table:
|
Present State
|
Next State
|
|
|
Input a
|
Input b
|
|
|
à q1
|
q1
|
q2
|
|
*q2
|
D
|
q2
|
|
D
|
D
|
D
|
3)Transition function:
δ( q1, a)= q1 ,δ
(q1,b)= q2
δ( q2, a)= D ,δ (q2,b)= q2
δ( D, a)= D ,δ (D, b)= D
Here the question suggests that a^nb^n that means b should follow a always like the solution in question 10, here you have taken baab??? I think the solution woulde be different ,similar to Q10 but a little different. the solution here doesn't seem true.
ReplyDelete