patternMinor
Language equivalency for modified CFG closed over intersection
Viewed 0 times
closedcfglanguageovermodifiedforintersectionequivalency
Problem
Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both between CFGs and between other CFG+'s.
Consider non-context-free language:
$$
\{ a^nb^nc^n|n≥0\}
$$
With the addition of intersections, consider the following "CFG+":
$$
S\rightarrow AB\ \&\ CD
$$
$$
A\rightarrow aAb\ |\ \epsilon
$$
$$
B\rightarrow cB\ |\ \epsilon
$$
$$
C\rightarrow aC\ |\ \epsilon
$$
$$
D\rightarrow bDc\ |\ \epsilon
$$
As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.
It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?
Consider non-context-free language:
$$
\{ a^nb^nc^n|n≥0\}
$$
With the addition of intersections, consider the following "CFG+":
$$
S\rightarrow AB\ \&\ CD
$$
$$
A\rightarrow aAb\ |\ \epsilon
$$
$$
B\rightarrow cB\ |\ \epsilon
$$
$$
C\rightarrow aC\ |\ \epsilon
$$
$$
D\rightarrow bDc\ |\ \epsilon
$$
As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.
It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?
Solution
It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar.
Here is more quote from that article on Wikipedia.
The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.
Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.
A related problem is the expressive power of intersections of context-free languages.
An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\{a_1^{n_1} a_2^{n_2} \cdots a_{d}^{n_{d}} b_1^{n_1} b_2^{n_2} \cdots b_d^{n_d} \mid n_1,n_2,\ldots ,n_d\ge 0\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.
Here is more quote from that article on Wikipedia.
The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.
Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.
A related problem is the expressive power of intersections of context-free languages.
An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\{a_1^{n_1} a_2^{n_2} \cdots a_{d}^{n_{d}} b_1^{n_1} b_2^{n_2} \cdots b_d^{n_d} \mid n_1,n_2,\ldots ,n_d\ge 0\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.
Context
StackExchange Computer Science Q#137074, answer score: 4
Revisions (0)
No revisions yet.