2
$\begingroup$

When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are closed under intersection. Now, I am having many difficulties in drawing PDAs especially the ones that are apparently the intersection of two other PDAs. For example, suppose I am asked to build the PDA for $$\{w \mid w \text{ is a palindrome and w has at most two 0s } \}$$

I think I would be able to build a PDA that recognises palindromes (which is one of the easiest ones), and also one that recognises a language that has at most two $0$s. But I am having many difficulties in building a PDA for the language above.

Apparently CFG are not closed under intersection, so I suppose there's no mechanical way of coming out with a solution for an intersection of two languages. Since this might be the case, do you have any suggestions on how could I start thinking on how to draw a PDA that is apparently the intersection of two other languages?

Note that I am asking for techniques to come up with PDAs for languages that are the conjunction of other simpler languages and not for a solution for the particular case above.

$\endgroup$
  • $\begingroup$ Yes, CFLs aren't closed with respect to intersection, For a simple example, $\{ a^n b^m c^m \} \cap \{ a^m b^m c^n \} = \{ a^n b^n c^n \}$, which isn't context free, while the first two are. $\endgroup$ – vonbrand Jan 27 '16 at 2:22
2
$\begingroup$

The intersection of a CFL and a regular language is itself a CFL. There is a standard construction for computing this intersection. It's documented in automata theory textbooks; look in your favorite automata theory textbook, and you should find it there.

$\endgroup$
2
$\begingroup$

The idea of the construction is quite simple: Run a DFA and a PDA in parallel, accepting if both do. Much like the construction for intersection between DFA-accepted languages.

Take a DFA and a PDA accepting by final state. You build a PDA whose states are pairs, a state of the DFA and a state of the PDA. Your combined transition function follows the DFA in the first component, and uses the other component of the state and the stack to follow the PDA's computation. You accept when both automata do, i.e., final states are pairs of a final state of the DFA and a final state of the PDA.

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