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)
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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 \} $.
-
$\begingroup$ @HendrikJan You're right! I'll edit but will keep my blunder so your valuable comment still makes sense. $\endgroup$– KaiAug 31 at 21:58
-
$\begingroup$ I'm not very proud of my new example. Is there a simpler one? $\endgroup$– KaiAug 31 at 22:12
-
1$\begingroup$ I have added an example directly into your answer so you don't have to copy it. Hope you don't mind. $\endgroup$ Sep 1 at 0:43
-
$\begingroup$ @HendrikJan not at all. Thanks for finding the Liu/Weiner paper! $\endgroup$– KaiSep 1 at 0:50
$\begingroup$
$\endgroup$
What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages?
The answer is no.
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.
$\begingroup$
$\endgroup$
1
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}\}$.
-
2$\begingroup$ Two PDAs can match that though, one can check both on if the
as andbs are equal, then also check if thecandds are equal. Then the other can check if the other side by side pairs are equal. $\endgroup$ Sep 1 at 8:19