Find dfa for the following language on Σ = {a, b}
L = {ab4wb2: w ∈ {a, b}* }
Solution:
This is pretty straight forward. The first part of this language, ab4 ,I do not believe requires any explanation. Look for the sequence, "abbbb" and the order is not correct, trap the remaining input in a non-accept state:
Now its time to tackle "wb2". This basically reads, "any combination of a's and b's or no a's and b's at all followed by 'bb'." At this stage, valid input should have a state of 'q5'. It is known that input should end with 2 b's so lets add those now and then connect the dots.
However, since there are still aspects missing. Namely,
let 'l' = lambda
d(a, q5) =
d(l, q5) =
d(a, q6) =
Lets solve from top to bottom. The language says that any string finishing in 'bb' should be accepted. At q5, this indicates that input of 'a' or 'l' should loop in place until a 'b' is encountered. Once this 'b' is encountered, the state will change to q6. But to get to an accepting state, we need consecutive b's. So if an 'a' is encountered while in state q6, it is safe to move back to q5 and begin the search for 'bb' over again.
d(a, q5) = q5
d(l, q5) = q5
d(a, q6) = q5
But this isn't finished! This just finds two consecutive b's. This is a DFA so all nodes must have an equation for all input. Namely,
d(a, q7) =
d(b, q7) =
must have a solution. Obviously, if another b is encountered, the state should not change. If this isn't obvious, notice that 'bb' and 'bbb' and 'bbbbbbbb' all end in 'bb'. But what if an 'a' is encountered? Well, then its back to looking for two consecutive b's. So,
d(a, q7) = q5
d(b, q7) = q7
Finally, the solution:
like it
ReplyDelete