The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number.

The only thing I have achieved is to get an automaton that recognizes $(a^n)(b^n)$ but that's only part of what I need.

Thanks a lot for your help.

  • $\begingroup$ What did you try? Where did you get stuck? This is a fairly standard exercise question and you'll probably get more from it by figuring it out yourself than from people telling you how to do it. One approach would be to write down a grammar for the language (which should be fairly straightforward) and then use the standard techniques for turning that into an automaton. $\endgroup$ Dec 19, 2016 at 21:38
  • $\begingroup$ @DavidRicherby I tried to recognize words of the form ab so that the number of as is equal to the number of bs, but I will try to find the proper grammar. $\endgroup$
    – alberto
    Dec 19, 2016 at 21:41
  • $\begingroup$ Hint: come up with a grammar and use the canonical translation into automata. $\endgroup$
    – Raphael
    Dec 19, 2016 at 23:38
  • 1
    $\begingroup$ Related: Constructing a PDA for the language $\{a^mb^n\mid m<2n<3m \}$ which has one extensive answer using grammars by Gilles, and a shorter one with a sufficient hint for a PDA by Yuval. $\endgroup$ Dec 20, 2016 at 1:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.