Register

GATE IT 2008 | Question: 35

• edited by
14,007 views
37 37 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

5 Answers

Best answer
45 45 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
5 5 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.

2 2 votes

L1: Every finite language is regular.

L2: Not Regular.Comparison required.

L3: DFA can be drawn.Regular

Examples of Deterministic finite automata

1 1 vote
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.
0 0 votes

L1 :  Finite language (n≤10000)                                                 Hence, Regular

L2 :  Needs matching with reverse (palindromes)                     Hence, CFL but not Regular

L3 :  Only parity (even/odd) of 0's and 1's matters                    Hence, Regular

 

Those who might be having doubt regarding L3  

that here we need to remember even or odd no.'s   But  Regular lang. can't remember

then, Regular Lang. cannot remember an unbounded amount 

but 

A regular language can remember a finite amount of information.


Hence, Opt. D is true

 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2008 | Quest...Next → · GATE IT 2008 | Quest...
← Previous in category · GATE IT 2008 | Quest...Next in category → · GATE IT 2008 | Quest...
Position:
Show:

Related questions

70 70 votes
8 answers 8 answers
23.9k
23.9k views
Ishrat Jahan asked Oct 28, 2014
23,941 views
GATE IT 2008 | Question: 36
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...
58 58 votes
7 answers 7 answers
23.2k
23.2k views
Ishrat Jahan asked Oct 28, 2014
23,167 views
GATE IT 2008 | Question: 34
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...
42 42 votes
4 answers 4 answers
10.3k
10.3k views
Ishrat Jahan asked Oct 28, 2014
10,330 views
GATE IT 2008 | Question: 33
Consider the following languages.$L_1 = \{a^i b^j c^k \mid i = j, k \geq 1\}$$L_2 = \{a^i b^j \mid j = 2i, i \geq 0\}$Which of the following is true?$L_1$ is not a CFL bu...
46 46 votes
5 answers 5 answers
15.5k
15.5k views
Ishrat Jahan asked Oct 28, 2014
15,545 views
GATE IT 2008 | Question: 32
If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet $\{a, b\}$ will be accepted by the new...