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

$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
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 ...
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.

0
Then, D will be the answer.
c is the right answer...... as L3 is not CFL.....L3 is CSl