0

My textbook discusses Context Free Grammars, and provides the following rules:

A -> 0A1

A -> B

B -> #

The resulting string is 000#111. Shouldn’t it just be 0#1? My steps:

A

0A1

0B1

0#1

I’m missing something obvious, what it is?

How do I know how many times to repeat a replacement when generating a grammar?

Moshe
  • 265
  • 1
    Hi. I do not understand. The grammar generates all words of the form $0^n$#$1^n$, in particular 000#111 and 0#1.. Recall that A has two options, you can take any of them any time. – Phicar Nov 19 '14 at 17:25
  • You can apply grammar rules as much as you want if it is permissible. – pointer Nov 19 '14 at 17:25
  • That grammar generates all strings of the form $0^n#1^n$ with $n\ge 1$. There isn’t a single resulting string. The derivation $A\to 0A1\to 0B1\to 0#1$ produces $0#1$, and the derivation $$A\to 0A1\to 00A11\to 000A111\to 000B111\to 000#111$$ yields $000#111$. – Brian M. Scott Nov 19 '14 at 17:25
  • So my string is valid too? – Moshe Nov 19 '14 at 17:27
  • @Moshe: It is indeed. – Brian M. Scott Nov 19 '14 at 17:28
  • Awesome, thanks. Someone should fix this textbook. And write an answer please, so I can accept it. – Moshe Nov 19 '14 at 17:29

0 Answers0