2
$\begingroup$

I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages:

Intersection of L1 and L2

L1 = L (aaa* bab)
L2 = L (aab* aba)

I can't tell if this is even possible because I don't see any common string that would be in both languages.

If it is not possible how should I formally state so? I am brand new to PDAs.

$\endgroup$
3
$\begingroup$

If the intersection is empty then you have to show that some PDA accepts the empty language. That doesn't sound too difficult.

More generally, every NFA is secretly a PDA (showing that every regular language is context-free), and so if you can construct an NFA for your language then you can easily convert it to a PDA.

| cite | improve this answer | |
$\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.