8,331 views

4 Answers

Best answer
39 votes
39 votes

$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 is option B.

edited by
19 votes
19 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 :-

B

6 votes
6 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
Answer:

Related questions

27 votes
27 votes
3 answers
1
go_editor asked Apr 23, 2016
8,416 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$
43 votes
43 votes
6 answers
2
Kathleen asked Sep 21, 2014
13,294 views
Consider the following Finite State Automaton:The language accepted by this automaton is given by the regular expression$b^*ab^*ab^*ab^*$$(a + b)^*$$b^*a(a+b)^*$$b^*ab^*a...
39 votes
39 votes
2 answers
3
Kathleen asked Sep 21, 2014
14,063 views
Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$$\left\{wxw^R \mid x, w \in \{0, 1\}...
32 votes
32 votes
4 answers
4
Kathleen asked Sep 21, 2014
11,439 views
A minimum state deterministic finite automaton accepting the language$L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respective...