3
$\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$?

$\endgroup$
  • $\begingroup$ If I may, I am curious as to why you asked that question. $\endgroup$ – babou Jun 10 '13 at 19:43
4
$\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.

$\endgroup$
  • 2
    $\begingroup$ Could you please include some more details to make the answer more self-contained? $\endgroup$ – Dave Clarke Mar 11 '13 at 21:14
  • 1
    $\begingroup$ Tanks! This is what I was looking for :-) $\endgroup$ – Ronny Mar 11 '13 at 22:53
  • 1
    $\begingroup$ Added a summary of the proof to make it more self-contained. $\endgroup$ – Jurij Mar 12 '13 at 20:21
1
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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