Register

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

• recategorized
1,804 views
0 votes
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
• recategorized
User Avatar

1 Answer

2 votes
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!
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
3 answers
1
go_editor asked Jul 20, 2016
1,269 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)$
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)$
User Avatar
1 votes
1 votes
1 answer
3
go_editor asked Jul 20, 2016
1,545 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 S_1 \lambda ; S_1 \rightarrow bS_1c \mid \lambda$
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...
User Avatar
1 votes
1 votes
2 answers
4
go_editor asked Jul 20, 2016
3,581 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 \}$ is 3 4 5 6
The number of states in a minimal deterministic finite automaton corresponding to the language $L=\{ a^n \mid n \geq 4 \}$ is3456
User Avatar
Link Copied!