4 votes

Which of the following grammars generate regular language?

a. S $\rightarrow$ aSa | bSb | a

b. S $\rightarrow$ aS | bS | aA | bA

A $\rightarrow$ bAc | $\epsilon$

c. S $\rightarrow$ aA | $\epsilon$

A $\rightarrow$ Sb

d. None of these

Why (A) is not regular? as {WCW^r | W,C belongs to (a,b)} is regular}

2 votes

Best answer

0

Yes, when that intermediate symbol belongs to the alphabet, then it should be a regular language.. https://gateoverflow.in/12374/gateoverflow.in

1

X in the example in mentioned link , is not just a symbol, from that X we can generate all strings as there X $\in \{a,b\}^*$ .

0 votes

As a rule of thumb, the production rules for type-3 grammar are restricted to following two types :

- $X \rightarrow a$
- $X \rightarrow a Y$

where $X$ and $Y$ are variables, and $a$ is terminal.

Hence, the correct option is D.

Refer this link for more details.