recategorized by
3,040 views
0 votes
0 votes

Consider the following two languages :

$L_1 = \{ x \mid \text{ for some y with } \mid y \mid = 2^{\mid x \mid} , xy \in \text{ L and L is regular language} \}$

$L_2=\{ x \mid \text{ for some y such that } \mid x \mid = \mid y \mid , xy \in \text{ L and L is regular language}\}$

Which one of the following is correct ?

  1. Only $L_1$ is regular language
  2. Only $L_2$ is regular language
  3. Both $L_1$ and $L_2$ are regular languages
  4. Both $L_1$ and $L_2$ are not regular languages
recategorized by

3 Answers

0 votes
0 votes
Both L1 and L2 are regular lang.
0 votes
0 votes

L1 is in The Form of X^(n) Y^(2^n) and We that it is a NON-REGULAR language.

L2 is in THE Form of X^n Y^n  and It is Well defined case of PDA and This language is also not regular.

Both L1 & L2 are not regular.

Hence Option(D) is Correct.

0 votes
0 votes
L = {a^n b^m | m  = n&& m,n>=1}. Then we know it is not regular because we have to compare number of occurences of “a” with number of occurences of “b” . But if it is given that  L = {a^n b^m | m  = n && m,n>=1} is regular then m and n has to be finte. Otherwise we cant say L is regular.

Using the above argument we can say L is finite and L1,L2 are subset of L. Hence L1,L2 are also regular.

Related questions

1 votes
1 votes
3 answers
1