CODEWITHSUNDEEP
context-free-grammar
ShadyBears
ShadyBears

Reputation: 4185

Context-Free Grammar

I need help understanding this concept.

The book states 

G1:
    A→0A1
    A→B
    B→#

it states that G1 generates the string 000#111

and shows a process

A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111

I understand what is happening in here. What I'm unsure of is if it can be infinitely looped.

For example:

can G1 also generate 0#1 using this process

A → 0A1 → 0B1 → 0#1

The book doesn't explain this part as clearly. Thanks

Upvotes: 2

Views: 200

Answers (2)

uba
uba

Reputation: 2031

Yes, any production can be applied an infinite number of times, thereby generating (in this and in most cases) an infinite number of strings. This grammar generates all strings of the form 0n#1n

Upvotes: 3

Bhushan Firake
Bhushan Firake

Reputation: 9458

Yes surely. The given grammar also generates the 0#1 language. The thing is clear enough. As you can see , the generated language 0#1 is a subset of the former language generated by the same grammar.

Upvotes: 0

Related Questions