CODEWITHSUNDEEP
formal-languages
Vinod Chelladurai
Vinod Chelladurai

Reputation: 539

Regular grammar - a*b*c*

I heard that a*b*c* is not regular. At the same time, i got the following regular grammar to generate it as well.

S → A
A → aA
A → B
B → bB
B → C
C → cC
C-> empty

Can anyone clarify is this grammar correct to generate a*b*c*

Thanks

Upvotes: 0

Views: 2544

Answers (2)

alienCoder
alienCoder

Reputation: 1481

a*b*c* is indeed regular. L={a^nb^nc^n | n>=0} is not regular.

Upvotes: 2

user2357112
user2357112

Reputation: 280227

a*b*c* is a perfectly regular language. In fact, the presentation is itself a proof that the language is regular; it's a regular expression in the classical sense.

The language you're probably thinking of is (a^n)(b^n)(c^n), or, since code formatting is a horrible substitute for TeX typesetting, the language of strings consisting of n a's, n b's, and n c's for all n. The important difference is that there must be the same number of a's, b's, and c's.

Upvotes: 2

Related Questions