0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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$ – David Richerby Dec 19 '16 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 '16 at 21:41
  • $\begingroup$ Hint: come up with a grammar and use the canonical translation into automata. $\endgroup$ – Raphael♦ Dec 19 '16 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$ – Hendrik Jan Dec 20 '16 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.