CODEWITHSUNDEEP
semanticscontext-free-grammarsyntactic-sugar
user1680944
user1680944

Reputation: 567

How to determine the corresponding language of a grammar?

I have the following grammar that uses center embedded recursion. However, it has two cases using an or: S-> aSbbb | aSbb | ϵ where ϵ is an empty set. Is there a way to generate a comprehensive mathematical formula (Language) that determines that grammar?

Upvotes: 1

Views: 79

Answers (1)

shaunc
shaunc

Reputation: 5611

The grammar is the "comprehensive mathematical formula". :) However, in the current case, it is easy to give an alternate description. Your grammar will generate strings of the form

a^nb^m

where s^i stands for "repeat the substring s i times", and

2n <= m <= 3n

n can also be 0 (empty string).

Upvotes: 1

Related Questions