3
$\begingroup$

Consider the context free grammar:

$$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$

It could generate regular language, which means it can be converted to a right linear grammar. Is there a general rule to convert CFG into a RLG? If there is no general rule, could you please show me how to convert this CFG to a RLG?

Improve this question
$\endgroup$
2
  • $\begingroup$ When you substantially change the question, or if you add other questions (like in this case), you should either clearly mark the edit, or if existing answers become invalid, you should create a separate question. $\endgroup$
    – Paresh
    Feb 7, 2013 at 15:17
  • $\begingroup$ Regarding the edit: The only (somewhat) hard part is finding out which language is generated by the CFG. After that, writing down the RLG is straightforward. $\endgroup$
    – Dominik D. Freydenberger
    Feb 8, 2013 at 12:34

3 Answers 3

Reset to default
8
$\begingroup$

Assuming you want your general method to be computable, the answer is no. When you consider a CFG that generates a regular language and convert it into a right-linear grammar, the size-increase is not bounded by any computable (or "recursive") function (first shown by Meyer and Fischer in this paper; also, if you can access it, this paper by Kutrib is a nice survey on the general area of non-recursive tradeoffs).

If a (computable) general conversion method existed, you could use it to construct a computable bound on the blowup between CFGs and right-linear grammars, which would contradict the non-existence of such a bound. Thus, knowing that your grammar generates a regular language does not help you at all.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice answer. I was not aware of the results you mentioned. $\endgroup$
    – Dan
    Feb 7, 2013 at 15:41
3
$\begingroup$

An undecidable property of context-free grammars is whether they generate all words over the alphabet. That implies that converting a context-free grammar into a linear grammar (if possible) should be difficult, since it is easy to decide whether a linear grammar (which is the same as an NFA) generates all words over the alphabet.

More accurately, we show that the following (type of) function is uncomputable: given a context-free grammar, either output an equivalent linear grammar, or output NO if the grammar represents a non-regular language.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ You are right but you slightly evaded the question ;) A more interesting questions is the following: how to construct an NFA from a CFG provided you know that the CFG generates a regular language. $\endgroup$
    – Dan
    Feb 6, 2013 at 15:53
  • 1
    $\begingroup$ In fact, you need a little more than uncomputability - you need "un-co-semi-computability". If you observe regularity is not co-semi-decidable (i.e., non-regularity is not semi-decidable), you can use Hartmanis' proof scheme (see here , or the survey by Kutrib I linked to below) to prove non-recursive tradeoffs, which in turn prove the non-existence of a conversion algorithm (see my answer). $\endgroup$
    – Dominik D. Freydenberger
    Feb 7, 2013 at 11:58
  • $\begingroup$ Do you know any details in this conntext regarding deterministic context-free or visibly pushdown languages? $\endgroup$
    – Dan
    Feb 7, 2013 at 15:44
  • 1
    $\begingroup$ From DCFL to DFA, I think it's something like a double-exponential tradeoff, according to Valiant, IIRC (Don't have time to check, don't know if the situation is better for VPL.) $\endgroup$
    – Dominik D. Freydenberger
    Feb 7, 2013 at 18:05
2
$\begingroup$

There's has been some work in Computational Linguistics on 'regular approximations' of context-free grammars -- converting CFGs into roughly equivalent regular grammars. A lot of this revolves the notion of a 'strongly-regular-grammar', this is a CFG that doesn't have self-embedding rules, such as A --> alpha A beta (like your rules), where alpha and beta are non-empty. Grammars with self-embedding are not regular languages, the problem being that further expansions of A by the same rule creates unbounded communication between the left and right, i.e. alpha^n A beta^N. In the other direction, Chomsky proved (the original paper is hard to find, see Harrison's book for the proof) that CFGs without self-embedding rules are regular (see this paper for a constructive proof).

The basic idea for dealing with self-embedding CFG grammars, like the ones you mention, is to convert them to strongly regular (i.e. non self-embedding) grammars -- there are efficient algorithms for doing this e.g. here, see this for review, and citations to original work) . The resulting 'strongly regular' grammar can then be converted into a finite-state automata, or perhaps some other type of regular grammar you're interested in.

Improve this answer
$\endgroup$
0

Your Answer

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

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