snippetMinor
How to convert a context free grammar (could generate regular language) to a right-linear grammar
Viewed 0 times
linearfreeconvertregularcouldlanguagegenerategrammarhowcontext
Problem
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?
$$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?
Solution
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.
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.
Context
StackExchange Computer Science Q#9542, answer score: 8
Revisions (0)
No revisions yet.