+23 votes
1.6k views

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
edited | 1.6k views

## 4 Answers

+24 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
0
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.
+1
@sonapraneeth option c are given All the three are context free show please select option D.
0

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

0
Ya we can say ...
+6 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.7k points)
+2 votes
c is the right answer...... as L3 is not CFL.....L3 is CSl
answered by (99 points)
+2 votes

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

answered by Loyal (9k points)
Answer:

+31 votes
1 answer
1
+23 votes
8 answers
3
+10 votes
2 answers
4
+20 votes
1 answer
6
+15 votes
3 answers
7