Could anybody help me design a PDA for the language $\{ 0^n 1^m | n ≠ m \}$?

Here is what I currently have:

enter image description here

  • $\begingroup$ Could you start from designing $n = m$ and then inversing the acceptance? $\endgroup$ – Evil Mar 21 '17 at 3:37
  • $\begingroup$ I have done this. What do you mean by inversing the acceptance? $\endgroup$ – user68104 Mar 21 '17 at 3:50
  • $\begingroup$ Is $n > 0$ and $m >0$ ? $\endgroup$ – Call_on_Duty Mar 21 '17 at 6:33

Hint : try to construct two PDA's for languages given below $$ \{0^n1^m : n > m\}, \quad \{0^n1^m : n < m\}. $$ Now combine the two PDA's for the language $$ \{0^n1^m : n \ne m\} $$

| cite | improve this answer | |
  • $\begingroup$ I constructed one for $n < m$ but I am stuck on $n > m$.. $\endgroup$ – user68104 Mar 21 '17 at 15:17

I quickly constructed and tested a PDA for this. It consists of three states:

  • $q_0:$ This is the initial state of the PDA. We stay here as long as we read 0's from the input. Every time we see a 0, we also put a 0 onto the stack. If the input starts with a 1, we make a transition straight to $q2$, and stay there as long as we read 1's. In this case the string will be accepted since there were no zeros; the amount of 1's can be anything (else than $\epsilon$). ALSO if we reach the end of the input and there is a 0 in the stack we can also move straight to $q_2$: this is the case where there are only 0's in the input; will be accepted.
  • $q_1:$ We move to this state with a transition from $q_1$ if we read a 1 and there is a 0 in the stack: this means that the input has both 0's and 1's. We stay in this state as long as we read 1's. The decision for accepting the string is based on the stack. If we reached the end of input (i.e. read an $\epsilon$) AND the stack is empty, then the string will be rejected, because this means that the amount of 1's and 0's were the same, which was not to be accepted. In the other case, where we reach the end but there is a 0 in the stack, we can move to the state $q_2$ because we know that now the amount of 1's is less than that of 0's. In addition, if the stack is empty and we still read a 1, we can also move to the state $q_2$: this indicates that there are more 1's than 0's; can be accepted.
  • $q_2:$ This is the final state of the PDA. We will read 1's and stay in this state as long as there is input left: we already know that the string will be accepted; the amount of 0's is either $\epsilon$ or less or more than that of 1's.

This PDA is of course nondeterministic but solves the problem nonetheless. Hope this helps you build the PDA!

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.