edited by
7,222 views
28 votes
28 votes

Which of the following languages is (are) non-regular?

  • $L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}$
  • $L_2 = \{w \mid w $ reads the same forward and backward$\}$
  • $L_3 = \{w \in \{0, 1\} ^* \mid  w$ contains an even number of 0's and an even number of 1's$\}$
  1. $L_2$ and $L_3$ only
  2. $L_1$ and $L_2$ only
  3. $L_3$ only
  4. $L_2$ only
edited by

3 Answers

Best answer
35 votes
35 votes

$L_1$ is regular.. since $10000$ is finite. So, finite states are required.

$L_3$ is also regular. We can make DFA for $L_3$. States will represent mod $2$ for $0$ and mod $2$ for $1$, which is finite

$L_2$ is non regular..It is CFG $S \rightarrow aSa \mid ... \mid zSz \mid \epsilon \mid [a-z]$

So, option is(D).

edited by
1 votes
1 votes

L1: The relation 0<=m<=n<=10000 is actually finite relation, and the strings would be finite.

Hence, REGULAR.

L2: Set of palindrome strings. They are definitely not regular. They are CFL.

L3: This DFA will be formed by product of two DFAs. 

DFA with even number of zeros : 2 states

DFA with even number of ones : 2 states

So total states required would be 2 x 2 = 4.

So DFA is possible, and hence it is a regular language.

So, option D is the right answer.

0 votes
0 votes
L1: Given language is bounded over a range.so it is regular. It is True

L2: only Turing machine reads from forward and backwards . It is False.

L3: even and an odd number is finite.so it is True.
Answer:

Related questions

56 votes
56 votes
6 answers
1
Ishrat Jahan asked Oct 28, 2014
12,431 views
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...
44 votes
44 votes
7 answers
2
Ishrat Jahan asked Oct 28, 2014
14,823 views
Consider a CFG with the following productions.$S \to AA \mid B$$A \to 0A \mid A0 \mid 1$$B \to 0B00 \mid 1$$S$ is the start symbol, $A$ and $B$ are non-terminals and 0 an...