I have the following PDA: enter image description here

And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} x\mid \mathrm{n}, \mathrm{m} \in \mathbb{N}^{+} \wedge x \in\{\mathrm{b}, \mathrm{c}\}^{*} \wedge| x |=\mathrm{m}\right\} $


$ \mathrm{L}_{\mathrm{PDA}} = \{a^*\} $

My problem is that I do not understand how to come up with this solution. If I had a DFA, it would not be a problem to find the language, but here i have to find two, and I have no idea how find them.

  • 1
    $\begingroup$ The same principle applies: guess and prove. In addition to how you approach DFAs, you want to look for matching stack operations: when are the same symbols pushed to and later popped off the stack? What's the pattern? $\endgroup$ – Raphael Feb 18 '19 at 12:13
  • $\begingroup$ The general procedures are described here: cs.stackexchange.com/q/18524/755. $\endgroup$ – D.W. Feb 18 '19 at 20:23
  • $\begingroup$ Thanks very much $\endgroup$ – Marie.L Feb 18 '19 at 20:51

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.