0
G ::= S
S ::= A M
A ::= a E | b A A
M ::= S | ϵ
E ::= a B | b A | ϵ
B ::= b E | a B B

where a and b are terminals

So I tried to do a derivation for this but I realized there's no point where you're left with just terminal variables? How do describe the grammar if it continuously goes in loops?

greenteam
  • 333
  • 1
    It can terminate. Here’s a terminating derivation: $$G\Rightarrow S\Rightarrow AM\Rightarrow aEM\Rightarrow aM\Rightarrow a$$ I used the productions $M\to\epsilon$ and $E\to\epsilon$ to get rid of the non-terminals. If it truly didn’t terminate, it would simply generate the empty language. – Brian M. Scott Sep 27 '16 at 19:53
  • Can you just completely delete the M because it can map to ϵ?? – greenteam Sep 27 '16 at 19:54
  • Yes; that’s what it means to have a production $M\to\epsilon$. You replace $M$ by the empty string, which effectively simply erases $M$. – Brian M. Scott Sep 27 '16 at 19:55
  • okay thanks! that answered my question, our professor didn't really explain what the ϵ term did. – greenteam Sep 27 '16 at 19:56
  • You’re welcome! – Brian M. Scott Sep 27 '16 at 19:59
  • one more question actually. If you were to do G => S => AM => bAAM

    you would end up with a b in the final result. Does that change what the grammar is doing?

     – greenteam Sep 27 '16 at 20:01
  • I didn’t actually try to work out what language the grammar generates: I just saw that it does generate a non-empty language. It certainly generates both words beginning with $a$ and words beginning with $b$, but without careful analysis I can’t tell you more than that. I have to run some errands and will be away from the computer for several hours, but I can take a look at it later this evening if you like. – Brian M. Scott Sep 27 '16 at 20:05
  • 1
    If i figure it out before then I'll leave a comment but other wise that would be great! thanks! – greenteam Sep 27 '16 at 20:06

0 Answers0