1
$\begingroup$

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$

$\endgroup$
  • $\begingroup$ Is $U$ a terminal? And as a hint: have you tried building a non-deterministic push-down automaton to recognise this language? $\endgroup$ – Peter Taylor May 21 '14 at 13:13
2
$\begingroup$

Probably $U$ denotes union, and you mean $L = \{ ba^nb^n \mid\ n\ge 0\} \cup \{ bba^nb^{2n} \mid\ n\ge 0\}$.

Yes that can be done by a deterministic PDA. The first two letters of the string decide how to handle the remainder of the string. Pushing the $a$'s and popping the $b$'s in appropriate ratio is a standard task.

$\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.