-1

The context free grammar: (e represents epsilon)

  S --> aSb|aSa|bSa|bSb|e

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?

2

1 Answer 1

1

There is no general algorithm for converting a CFG to a right-linear grammar because right-linear grammars generate precisely the regular languages, which are a strict subset of the context-free languages. Accordingly, if a general algorithm existed that performed this transformation, it would prove all context-free languages are regular, which is known to be false.

Hope this helps!

2
  • If there is no general rule to do that, could you show me how to convert the CFG above into a RLG?
    – henry
    Feb 7, 2013 at 13:54
  • @henry- If you look at the above grammar, you'll note that it generates all even-length strings made from a's and b's. Given that insight, you can try creating, from scratch, a right linear grammar that generates the same language. Feb 7, 2013 at 18:46

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