# Are 2 independent PDAs equivalent to a turing machine?

I was thinking about the language $$a^nb^nc^n$$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $$a$$ and $$b$$ and the second for $$b$$ and $$c$$ and they both accept, the construction would basically accept the language)

No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $$L = \{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\}$$. I conjecture that to express $$L$$ as the intersection of CFLs requires infinitely many CFLs.

The paper An infinite hierarchy of intersections of context-free languages by Liu and Weiner (Math. Systems Theory 7, 185–192 (1973). https://doi.org/10.1007/BF01762237) presents languages that can be written as intersection by $$k$$ context-free languages but not by intersecting $$k-1$$-languages. For $$k=3$$ the language is $$\{\; a^k b^\ell c^m a^k b^\ell c^m \mid k,\ell,m \in \mathbb{N}\}$$. Thus, that language is the intersection of three cf-languages, but not the intersection of two cf-languages. For other $$k$$ the same pattern is repeated. The quote that paper "The proof is quite complicated".

The language $$\{\textsf{a}^n\textsf{b}^n\textsf{c}^n\textsf{d}^n\textsf{e}^n~|~n\in\mathbb{N}\}$$ seems as complicated but is in fact the intersection of two cf-languages: $$\{ \textsf{a}^m\textsf{b}^m\textsf{c}^n\textsf{d}^n\textsf{e}^p \mid m,n,p\in \mathbb N \} \cap\{ \textsf{a}^m\textsf{b}^n\textsf{c}^n\textsf{d}^p\textsf{e}^p \mid m,n,p\in \mathbb N \}$$.

• @HendrikJan You're right! I'll edit but will keep my blunder so your valuable comment still makes sense.
– Kai
Commented Aug 31, 2023 at 21:58
• I'm not very proud of my new example. Is there a simpler one?
– Kai
Commented Aug 31, 2023 at 22:12
• I have added an example directly into your answer so you don't have to copy it. Hope you don't mind. Commented Sep 1, 2023 at 0:43
• @HendrikJan not at all. Thanks for finding the Liu/Weiner paper!
– Kai
Commented Sep 1, 2023 at 0:50

What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages?

To prove that, we can observe that, while the class of context-free languages is not closed under intersection, the class of context-sensitive languages is. This means that intersection of two CFLs is always a CSL (since every CFL is also a CSL). If you could represent language of every grammar as an intersection of two (or, in general, any $$k\in\mathbb{N}$$) CFLs, it would mean that every grammar has context-sensitive language, which we know is not true.
The language $$\{a^nb^nc^n | n \in \mathbb{N}\}$$ belongs to a strict subset of context-sensitive languages that can be expressed in terms of an intersection of two context-free languages.
Having two PDAs cannot recognize a language like $$\{a^nb^nc^nd^ne^n | n \in \mathbb{N}\}$$.
• Two PDAs can match that though, one can check both on if the as and bs are equal, then also check if the c and ds are equal. Then the other can check if the other side by side pairs are equal. Commented Sep 1, 2023 at 8:19