# MadeEasy Test Series: Theory Of Computation - Regular Languages

507 views

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
0
yes , ye wala bhi mera galat hua , pata nahi kyu ? :(

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
0

But Sir, in option A; a ∈ (a, b) .. Right?

0
"a" is a symbol.
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
Got it sir, thnx :)
0

Sir , from the first grammar I am able to generate the string baabab using productions :

S-->bSb-->baSab-->baaSab-->baabAab-->baabab

as well as string "baabaab" using productions S-->bSb-->baSab-->baaAab-->baabAaab-->baabaab

And both of these are not of the form wawr

0
a) "S $\rightarrow$ aSa|bSb|a "
0
So sorry I misread S from option b in first grammar, got it thankss.
0

@Praveen sir

a). L1={wlwRw∈{a,b}∗,l∈{a,b} }

which type of language is this DCFL or NDCFL? (note that l∈{a,b} not {a,b}*)

I feel its NDCFL can you also tell how PDA will look like?

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

1
546 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$ only Both Neither of the above