0
$\begingroup$

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free grammars that are not regular that are either right or left-linear?

$\endgroup$
  • 1
    $\begingroup$ Have you tried either writing a proof of this or looking for counterexamples? Commonly, the proof that every every regular language can be generated using either a right-linear or left-linear grammar takes an arbitrary DFA (or NFA) and explains how to create a right-linear or left-linear grammar having the same language. Can you do the same for the other direction? $\endgroup$ – roctothorpe Mar 19 '18 at 22:33
  • $\begingroup$ I have looked for several counterexamples, but so far I've only been able to come up with grammars that are a mixture of right and left-linear. This leads me to think that it isn't possible to create a right or left-linear grammar for a non-regular language, though I'm having a hard time coming up with an approach that proves it. $\endgroup$ – Emma Barrett Mar 20 '18 at 4:46
  • $\begingroup$ Why not begin with Google? en.wikipedia.org/wiki/Regular_grammar $\endgroup$ – xskxzr Mar 20 '18 at 15:30
  • $\begingroup$ You could give a procedure for turning an arbitrary right linear grammar into an NFA, thus showing that the grammar has to correspond to a regular language (the same can be done for an arbitrary left linear grammar). It may be helpful to think of what the possible production rules in a right linear grammar can look like and how those would correspond to states/transitions in an NFA. $\endgroup$ – roctothorpe Mar 22 '18 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.