edited by
7,757 views
22 votes
22 votes

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?

  1. Both $P$ and $Q$ are true.
  2. $P$ is true and $Q$ is false.
  3. $P$ is false and $Q$ is true.
  4. Both $P$ and $Q$ are false.
edited by

2 Answers

Best answer
61 votes
61 votes

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)^*$

edited by
9 votes
9 votes

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 

Answer:

Related questions

21 votes
21 votes
4 answers
3
Akash Kanase asked Feb 12, 2016
7,205 views
The Floyd-Warshall algorithm for all-pair shortest paths computation is based onGreedy paradigm.Divide-and-conquer paradigm.Dynamic Programming paradigm.Neither Greedy no...
15 votes
15 votes
4 answers
4