The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 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
asked in Theory of Computation by Veteran (96.1k points)
edited by | 2.2k views

4 Answers

+25 votes
Best answer

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)

answered by Active (4.2k points)
edited by
More appropriately, L3 is not a CFL. Saying it is a CSL doesn't mean it is not a CFL because the family of CFLs is a subset of the family of CSLs.
@sonapraneeth option c are given All the three are context free show please select option D.

Can we say L1 is regular Language as we can give a REGEX: as 0+1+

Ya we can say ...
+7 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
answered by Active (2.8k points)
Then, D will be the answer.
+2 votes
c is the right answer...... as L3 is not CFL.....L3 is CSl
answered by (105 points)
+2 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

answered by Loyal (7.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,122 answers
71,039 users