Register

Answer given as (C). Can't understand why ??

• retagged by
605 views

1 Answer

Best answer
7 7 votes
We can reduce this to

$$L = \{0^n1^n0^m \mid n\geq 0, m \leq n\}.$$

We cannot make a PDA for this as we need to do 2 indefinite counts. But we can do this with an LBA and so $L$ is CSL. Answer should be B choice.
• selected by
Voting & Accepting an answer helps improve the community
← Previous · Which of the followi...Next → · Calculating number o...
← Previous in category · Which of the followi...Next in category → · How to design PDA fo...
Position:
Show:

Related questions

2 2 votes
1 1 answer
2.1k
2.1k views
Mahesha999 asked Nov 20, 2016
2,060 views
Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows:A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in t...
3 3 votes
0 0 answers
942
942 views
Payal Rastogi asked Nov 2, 2015
942 views
What should be answers of Question 14, 15 and 16 and Why ??
Common Data for Q14,15 &16 is given below: Ram takes two context-free languages $L_1$ and $L_2$ a). He concatenates $L_1 $ and $L_2$ to obtain a new set $L_3$.b). He take...
0 0 votes
0 0 answers
229
229 views
Shubham Sharma 2 asked Sep 9, 2025
229 views
UGC NET CSE | August 2024 | Part 2 | Question: 3
If $L_{1}$ and $L_{2}$ are context free languages, which of the following is True about $L_{1} \cap L_{2}$?$\mathrm{L}_{1} \cap \mathrm{~L}_{2}$ is context free$\mathrm{L...
0 0 votes
0 0 answers
167
167 views
Shubham Sharma 2 asked Sep 9, 2025
167 views
UGC NET CSE | August 2024 | Part 2 | Question: 52
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy:Context-free languagesContext-sensitive lan...