edited by
9,199 views
36 votes
36 votes

Consider the languages $L1, \:L2 \:and \: L3$ as given below.

$L1=\{0^p 1^q \mid p, q \in N\}, \\ L2 = \{0^p 1^q \mid p, q \in N \:and \:p=q\} \: and, \\ L3 = \{0^p 1^q 0^r \mid p, q, r \in N\: and \: p=q=r\}.$ 

Which of the following statements is NOT TRUE?

  1. Push Down Automata (PDA) can be used to recognize $L1$ and $L2$
  2. $L1$ is a regular language
  3. All the three languages are context free
  4. Turing machines can be used to recognize all the languages
edited by

4 Answers

Best answer
38 votes
38 votes

Answer is C.

$L_{1}$ is RL

$L_{2}$ is CFL

$L_{3}$ is CSL

Turning Machine is powerful Machine.  It can be used to accept all the languages  (RL, CFL, CSL, RE)

edited by
9 votes
9 votes
L1 is Regular(no stack is required,it has a DFA) so obviously it is CFL

L2 requires one stack so it is CFL

L3 more than one stack is required-CSL

And every RL,CFL,CSL are Recursively Enumerable so accepted by TMs.

So C is answer
3 votes
3 votes

L1 = Regular because we can give a REGEX: 0+1+

L2 = equal number of 0's and equal number of 1's and after a "1" you can never see a "0"

Take a valid string from L2 = "0011"

Push all "0's"and for every "1" pop one "0" Hence it's DCFL because we know when and what to Push and Pop and every DCFL is CFL.

L= {0p1p0| p>0, p=q=r} and this is classic CSL.

p>0 because we have given p=q=r therefore I can write it as "p" in place of q and r and since p,q,r belongs to N (Natural Number) which makes p>0

Hence Answer is c) because L1 = L2 = CFL, but L3 = CSL, not CFL

Answer:

Related questions

18 votes
18 votes
2 answers
3
25 votes
25 votes
2 answers
4