GATE CSE 2016 | Set 2 | Question: 17

Question

Language $L_{1}$ is defined by the grammar: $S_{1} \rightarrow a S_{1} b \mid \varepsilon$

Language $L_{2}$ is defined by the grammar: $S_{2} \rightarrow a b S_{2} \mid \varepsilon$

Consider the following statements:

• P: $L_{1}$ is regular
• Q: $L_{2}$ is regular

Which one of the following is TRUE?

• A. Both $P$ and $Q$ are true.
• B. $P$ is true and $Q$ is false.
• C. $P$ is false and $Q$ is true.
• D. Both $P$ and $Q$ are false.

Comments

L1 is generating equal no. of a and b -> CFL
L2 is generating (ab)* -> Reg

---

Most Simplest Way to Check :

L1 = { a^n b^n | n >= 0 } (infinite dependency over 2 symbols ; so non regular)

L2 = { (ab)^n | n >= 0 } (here no dependency; so regular)

Answer 1

Answer is C.

$S_1\rightarrow aS_1b\mid \epsilon$

$L_1 = \{ a^nb^n \mid n\geq 0\}$ is CFL

$S_2\rightarrow abS_2\mid \epsilon$

$L_2 = \{ (ab)^n \mid n\geq 0\}$ is Regular having regular expression $(ab)^*$

Comments

doubt cleared!

---

Just to add.. We have to be careful while checking

This question is asking for checking whether language generated by given grammar are regular or not..

But there are some questions like this :

https://gateoverflow.in/3491/gate2007-it-49

Where they ask for checking whether given grammars itself are regular are not..

---

note: left linear or right linear grammer means regular. So l2 is regular

Answer 2

L2 is Right  Linear Grammar L1 is neither right  or left linear grammar  , A regular language either should be Left or Right linear grammar , but not both  so solution is L2 is regular but L1 is not 

Comments

@Sandeep Verma

There is a small flaw in your answer...

The question asks for checking whether language generated by given grammar is regular or not..

We can't eliminate option based on the regularity of grammar..

I mean there are some grammars which are not regular but still produce regular grammar..

For example, S-->aSa/epsilon is not a regular grammar but still it produces a regular grammar aa*.

 

 

---

But,  S-->aSa/epsilon doesn’t have the Regular expression aa*.

Since , by using aa*, we can generate the string ‘aaa’.

But the grammar S-->aSa/epsilon can’t generate ‘aaa’ .

 

Correct me, If I am wrong.

---

(aa)*