The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:

  1. not recursive

  2. is recursive and is a deterministic CFL

  3. is a regular language

  4. is not a deterministic CFL but a CFL

asked in Theory of Computation by Veteran (69k points) | 851 views

4 Answers

+19 votes
Best answer

$L=\left\{0^i21^i \mid i \geq 0\right\}$ has only one comparison that can be done using a DPDA. Hence, its DCFL.

Context free languages are a proper subset of Recursive Languages. $\therefore$ it is recursive too.

answer = option B

answered by Veteran (31k points)
selected by
+13 votes

L = {0i21i |  i>=0 } is deterministic CFL,

Evert DCFL is recursive. As we have membership algorithm for DCFL (Or say CFL in general) , that's why it is recursive. In fact DCFL is subset of Recursive Languages.

SO answer :-


answered by Veteran (49.5k points)
+5 votes
push all 0  then skip 2 then for every 1 pop one 0 .. done by 1 stack without any confusion.. so dcfl.

dcfl⊆ cfl ⊆ csl ⊆ rec ⊆re
answered by Veteran (60.4k points)
transition for skip ??? i am getting little bit confused there ....
yes when 2 will come we don't need to perform any operation, therefore, we will bypass (skip) 2 and then perform a pop operation on seeing 1
+2 votes
The answer is B.
answered by Veteran (19.8k points)

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

33,705 questions
40,252 answers
38,860 users