0
$\begingroup$

Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$.

if we have $a$ This side of the string, on the other side of the string we have $aa$. and if we have $b$ This side of the string, on the other side of the string we have $bb$.

Examples of words in this language (middle point emphasized):

$ab\, bbaa$

$aaa\, aaaaaa$

$bab\, bbaabb$

What is a PDA accepting this language?

I can find a grammar for this language but I can't find a PDA.

The grammar: $S \to aSaa \mid bSbb \mid aaa\mid bbb$

$\endgroup$
1
$\begingroup$

There are general constructions that give a PDA given a CFG.

In this case, start with the PDA for $\{a^n b^n \colon n > 0\}$, instead of storing one $A$ on the stack for each input $a$, store two, and the same for $b$. When reaching the middle, start discounting and accept by empty stack.

$\endgroup$

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.