4
$\begingroup$

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)

$\endgroup$
0

3 Answers 3

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @HendrikJan You're right! I'll edit but will keep my blunder so your valuable comment still makes sense. $\endgroup$
    – Kai
    Aug 31, 2023 at 21:58
  • $\begingroup$ I'm not very proud of my new example. Is there a simpler one? $\endgroup$
    – Kai
    Aug 31, 2023 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, 2023 at 0:43
  • $\begingroup$ @HendrikJan not at all. Thanks for finding the Liu/Weiner paper! $\endgroup$
    – Kai
    Sep 1, 2023 at 0:50
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – mousetail
    Sep 1, 2023 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.