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} Theory of Computation made-easy-test-series theory-of-computation regular-language + – Tushar Shinde asked Jan 25, 2016 edited Mar 5, 2019 by akash.dinkar12 Tushar Shinde 1.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply worst_engineer commented Jan 25, 2016 reply Follow Share yes , ye wala bhi mera galat hua , pata nahi kyu ? :( 0 votes 0 votes Please log in or register to add a comment.
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. Praveen Saini answered Jan 25, 2016 selected Jan 25, 2016 by Tushar Shinde Praveen Saini comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Praveen Saini commented Jan 25, 2016 reply Follow Share a) "S $\rightarrow$ aSa|bSb|a " 0 votes 0 votes radha gogia commented Jan 25, 2016 reply Follow Share So sorry I misread S from option b in first grammar, got it thankss. 0 votes 0 votes Denson George commented Jan 10, 2017 reply Follow Share @Praveen sir a). L1={wlwR∣w∈{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 0 votes Please log in or register to add a comment.
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. Gaurav Sharma answered Jan 25, 2016 Gaurav Sharma comment Share Follow See all 0 reply Please log in or register to add a comment.