1

I need help to construct a right-linear grammar for the language {w ∈ {a,b}* | w does not end in aa}.

I have constructed the regular grammar for the language {w ∈ {a,b}* | w does not end in aa}, as below

S -> aA | bB | ε

A -> aC | bB | ε

B -> aA | bB | ε

C -> aC | bB

How can I construct a right-linear grammar for the same?

icktoofay
  • 126,289
  • 21
  • 250
  • 231
gigmeg01
  • 11
  • 1
  • Welcome to Stack Overflow. You may find more help related to your topic on [ComputerScience.StackExchange](http://cs.stackexchange.com/). – Patrick M Oct 21 '14 at 22:30
  • Give it a try: http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932 – Grijesh Chauhan Oct 23 '14 at 02:43

1 Answers1

1

Your grammar is already right-linear, since:

  1. For every rule, there is only one non-terminal on the right hand side
  2. The non-terminals appear only at the end
justhalf
  • 8,960
  • 3
  • 47
  • 74