# How to convert a context free grammar (could generate regular language) to a right-linear grammar

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?

-
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. –  Paresh Feb 7 '13 at 15:17
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. –  Dominik D. Freydenberger Feb 8 '13 at 12:34

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.

-
Nice answer. I was not aware of the results you mentioned. –  Dan Feb 7 '13 at 15:41

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.

-
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. –  Dan Feb 6 '13 at 15:53
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). –  Dominik D. Freydenberger Feb 7 '13 at 11:58
Do you know any details in this conntext regarding deterministic context-free or visibly pushdown languages? –  Dan Feb 7 '13 at 15:44
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.) –  Dominik D. Freydenberger Feb 7 '13 at 18:05