Generating grammar

Computer Science Level 4

$\displaystyle S\to ABS\mid AB$

$\displaystyle A\to \text{aaa}A\mid \epsilon$

$\displaystyle B\to B\text{bb}\mid \epsilon$

$\displaystyle A\text{bb}\to A$

The above grammar generates a language that is which of the following?

Regular but not finite Finite Not Context-Free Context-Free but not regular

1 solution

Maggie Miller
Jul 21, 2015

The generated language is $L=L((\text{aaa}\cup\text{bb})^*)$ ; or in English, words in $\{\text{a},\text{b}\}^*$ so that consecutive strings of a's have length divisible by three and consecutive strings of b's have length divisible by two.

This language is clearly infinite, since $\text{b}^{2n}\in L$ for each $n$ . It is also regular, since $L$ is decided by the following Finite State Machine.

Therefore, the answer is regular but not finite .

Generating grammar

1 solution

0 pending reports