CODEWITHSUNDEEP
grammarcontext-free-grammarautomatafinite-automatacontext-free-language
asdf
asdf

Reputation: 1

How can I show this language is context free by constructing a context free grammar?

How can I construct a context free grammar for the following language:

L = {0^n1^nx | n >= 1, and x ∈ {0, 1}*}

This language is that some number of zeros followed by same number of ones then some number of bit strings. I was thinking I need S -> 0S1 for the 0^n1^n part and A -> 0A | 1A | e for the x ∈ {0, 1}*. Since I need some bit strings after same number of zeros and ones, I did

S -> 0S1A | e

A -> 0A | 1A | e

But the grammar accepts 0001101, which is not correct. There are 3 0's and only 2 1's. I am new to CFG's. Can someone give me a tip for this language?

Upvotes: 0

Views: 285

Answers (1)

rici
rici

Reputation: 241911

Whenever you have a language which can be decomposed into the concatenation of two sublanguages, construct the two languages separately and then concatenate them:

S → A B
A → …
B → …

In this case, A will be 0n1n and B will be {0, 1}*.

Upvotes: 1

Related Questions