4
$\begingroup$

It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ and one (a DFA) that accepts $R$. Than a further automaton (a PDA) is constructed that accepts $L \cap R$. This automaton can be converted to a context-free language.

Is there some literature that gives a proof without constructing automatons and constructs a context-free grammar that generates $L \cap R$ directly?

What I want to know actually: Given a context-free Language $L$ and a regular Language $R$. How many rules at most does a context-free grammar need to generate $L \cap R$?

Improve this question
$\endgroup$
1
  • $\begingroup$ If I may, I am curious as to why you asked that question. $\endgroup$
    – babou
    Commented Jun 10, 2013 at 19:43

2 Answers 2

Reset to default
5
$\begingroup$

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

A summary of the proof given in the link. First, it is shown that proving $L \cap R$ is CFL reduces to proving that $L \cap R'$ is CFL, where $R'$ is a regular language recognized by a DFA with exactly one final state. Then from the grammar for L (in Chomsky normal form) and DFA for R' a new grammar for $L \cap R'$ is constructed using a few straightforward rules.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Could you please include some more details to make the answer more self-contained? $\endgroup$
    – Dave Clarke
    Commented Mar 11, 2013 at 21:14
  • 1
    $\begingroup$ Tanks! This is what I was looking for :-) $\endgroup$
    – Ronny
    Commented Mar 11, 2013 at 22:53
  • 2
    $\begingroup$ Added a summary of the proof to make it more self-contained. $\endgroup$
    – Jurij
    Commented Mar 12, 2013 at 20:21
2
$\begingroup$

This is a classical cross-product construction, originally published by Bar-Hillel, Perles and Shamir (1961) in On formal properties of simple phrase structure grammars.It can be found in most elementary books on automata theory. (the reference to the initial paper appears in the paper suggested by @Jurij, which I could not access as I wrote this answer).

Actually, it can be done with any CF grammar, no normal form being required (but ... see below). On the FSA side, any recognizing finite-state automaton will do, including non-deterministic.

The complexity is $O(n^{p+1})$ for both the construction time and the size of the resulting grammar, where $n$ is the number of states of the automaton and $p$ is the length of the longest rule right-hand side of the grammar.

Hence, reducing the grammar in Chomsky normal form (CNF) will give $n=2$ and allow for cubic time and space (and result size) complexity. More precisely, some of the constraints of CNF are not even needed. It is enough to put it in 2-form, by introducing new non-terminal so that no right-hand side containt more than 2 symbols.

The size of the resulting grammar can be further reduced by minimizing the finite automaton.

Minimizing a DFA has a time complexity $O(ns \ log\ n)$, where $n$ is the number of states and $s$ is the size of the alphabet. However the cost is much higher for a NDFA, as it is $O(2^n)$. There is no escape from that if you have a NDFA to begin with, since this high cost is needed for determinizing the NDFA which requires a powerset construction on the set of states.

Improve this answer
$\endgroup$

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.