Register

UGC NET CSE | September 2013 | Part 2 | Question: 15

• edited by
2,364 views
0 0 votes

Consider the following two languages:

$L_1 =\{a^n b^l a^k \mid n+l+k > 5\}$

$L_2 =\{a^n b^l a^k \mid n> 5, l>3, k \leq l \}$

Which one of the following is true?

  1. $L_1$ is regular language and $L_2$ is not regular language
  2. Both $L_1$ and $L_2$ are regular language
  3. Both $L_1$ and $L_2$ are not regular language
  4. $L_1$ is not regular language and $L_2$ is regular language

1 Answer

2 2 votes
I think A is the answer.

L1 is regular but not L2.

In L2 we have to remember the value of l (no of b's) so that it can be compared with k.

regular grammar cannot remember a value (It has no stack)

Thus it is not regular

 

Correct me if i am wrong!
Voting & Accepting an answer helps improve the community
Answer:
← Previous · EXOR operation in CNext → · UGC NET CSE | Septem...
← Previous in category · UGC NET CSE | Septem...Next in category → · UGC NET CSE | Septem...
Position:
Show:

Related questions

4 4 votes
3 answers 3 answers
1.7k
1.7k views
go_editor asked Jul 20, 2016
1,703 views
UGC NET CSE | September 2013 | Part 2 | Question: 14
Regular expression for the language $L=w \in \{0,1\}* \mid w$ has no pair of consecutive zeros $\}$ is$(1+010)*$$(01+10)*$$(1+010)*(0+ \lambda)$$(1+01)* (0+\lambda)$
1 1 vote
1 answers 1 answer
4.1k
4.1k views
go_editor asked Jul 20, 2016
4,081 views
UGC NET CSE | September 2013 | Part 2 | Question: 17
Assume the statements $S_1$ and $S_2$ given as:$S_1$: Given a context free grammar G, there exists an algorithm for determining whether L(G) is infinite.$S_2$: There exis...
1 1 vote
1 1 answer
2.1k
2.1k views
go_editor asked Jul 20, 2016
2,134 views
UGC NET CSE | September 2013 | Part 2 | Question: 16
LL grammar for the language $L = \{a^n b^m c^{n+m} \mid m \geq 0, n \geq 0\}$ is$ S \rightarrow aSc \mid S_1 ; S_1 \rightarrow bS_1c \mid \lambda$$ S \rightarrow aSc \mid...
1 1 vote
2 answers 2 answers
4.0k
4.0k views
go_editor asked Jul 20, 2016
4,016 views
UGC NET CSE | September 2013 | Part 2 | Question: 13
The number of states in a minimal deterministic finite automaton corresponding to the language $L=\{ a^n \mid n \geq 4 \}$ is3456