I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition:

$\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $



Let us start with an automaton for ${2^rc^r}$ for the alphabet $\{2, c\}$. This is quite a standard example. As long as you are reading $2$ add a letter to the stack until you read the first $c$. Then for each $c$ pop a letter from the stack. The word and the stack should finish at the same time.

Now using this automaton we should be able to build one for you language, where the string of $c$s should turn to any concatenation of a staring of $a$s and a string of $b$s and the string of $2$s turns into a concatenation of a string of ones and a string of twos. This means for each zero you read push a letter to the stack until you read the first one. Then for each one push a letter to the stack until you read the first $a$ then for each $a$ pop a letter until you find the first $b$ and then pop for each $b$. The stack should turn empty upon reading the last letter in the world. Note that the DPA should rejects the string if at any point it reads an unexpected letter (a $0$ after an $a$ for example).

Note that one of the substrings might be empty, so you should consider the case of starting with $a$s directly after zeroes for example.

  • 1
    $\begingroup$ Thank you, this helped me to construct de automaton. Thanks! $\endgroup$ Dec 15 '19 at 13:07
  • $\begingroup$ @SebasBelaustegui You can accept an answer by clicking on the checkmark to the left if it answers your question :) $\endgroup$ Dec 15 '19 at 13:46

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.