The Gateway to Computer Science Excellence
+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} 

in Theory of Computation by Active (2.2k points)
edited by | 446 views
yes , ye wala bhi mera galat hua , pata nahi kyu ? :(

2 Answers

+2 votes
Best answer

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. 

by Veteran (57.1k points)
selected by

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

"a" is a symbol.
Yes, when that intermediate symbol belongs to the alphabet, then it should be a regular language..
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\}^*$ .
Got it sir, thnx :)

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


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

And both of these are not of the form wawr

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

@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?

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. 

by Active (2.6k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,736 answers
107,922 users