edited by
1,199 views
4 votes
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} 

edited by

2 Answers

Best answer
2 votes
2 votes

if we look carefully at Grammars given, Languages corresponding to them are 

a). $L_1=\{waw^R \; \mid \; w \in \{a,b\}^*\}$

b). $L_2=\{wb^nc^n \; \mid \; w \in \{a,b\}^+,n\geq 0\}$

c). $L_3=\{a^nb^n \; \mid \; n\geq 0\}$

None of these are regular. 

selected by
0 votes
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. 

Related questions

5 votes
5 votes
3 answers
1
Hirak asked May 25, 2019
1,729 views
Consider the following statements:$S_1:\{(a^n)^m|n\leq m\geq0\}$$S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $Which of the following is regular?$S_1$ only$S_2...
0 votes
0 votes
1 answer
2