Project ForgeConsider a finite automaton with states q0 (start, non-accepting), q1 (accepting), q2 (accepting), and q3 (accepting, but unreachable from q0). Transitions: q0 has a self-loop on 'b' and goes to q1 on 'a'. q1 has a self-loop on 'b' and goes to q2 on 'a'. q2 has a self-loop on 'b' and goes back to q1 on 'a'. (q3 has outgoing edges to q1 on 'a' and q2 on 'b', but nothing transitions INTO q3, so it never affects the accepted language.) The language accepted by this automaton is given by the regular expression
- Ab*ab*ab*ab*
- B(a+b)*
- b*a(a+b)*
- Db*ab*
Explanation
From q0, any number of b's are consumed via self-loop before the first 'a' moves to q1. Once in {q1,q2} (both accepting), 'a' just toggles between q1 and q2 while 'b' self-loops at whichever state you're in — so once you reach q1, ANY subsequent combination of a's and b's keeps you in an accepting state. So the language is b* a (a+b)* — any number of leading b's, then an a, then anything at all.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.