CODEWITHSUNDEEP
context-free-grammarformal-languages
Nitin
Nitin

Reputation: 175

Construct a CFG for

L1 = { a^i b^j | i,j>=0 }

My attempt:

S = SA|e

A = aAB|e

B = bB|e

I have no way to confirm my answer, is this correct?

Upvotes: 1

Views: 995

Answers (2)

Patrick87
Patrick87

Reputation: 28292

You define L1 = {a^i b^j | i, j >= 0}. In words, this is the language of all strings which begin with zero or more a's, and which end with zero or more b's. This is a regular language; a regular expression for it is a*b*. A regular grammar (also a context-free grammar) is the following:

S := lambda | aS | bT
T := lambda | bT

Another context-free grammar is the following:

S := lambda | aS | Sb

Sorry if I'm missing something and your language is more complicated than what I'm reading. If you have some reason to believe that L1 so defined is different from the language I have described, please explain.

Upvotes: 1

andrew cooke
andrew cooke

Reputation: 46862

It's not correct because there's no way to get a single "b" (or any number of "b"s without any "a"s).

(And I think you can fix it by changing just one letter ;o)

PS Sorry for earlier incorrect reply; thought it was for i=j.

Upvotes: 2

Related Questions