patternMinor
Are 2 independent PDAs equivalent to a turing machine?
Viewed 0 times
equivalentindependentarepdasmachineturing
Problem
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)
Solution
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 \} $.
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 \} $.
Context
StackExchange Computer Science Q#161826, answer score: 7
Revisions (0)
No revisions yet.