# 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. 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. 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). 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.) Feb 7 '13 at 18:05

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.