The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
856 views

Consider the languages:

  • $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$
  • $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol
  • $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$

Which one of the following is TRUE?

  1. $L_1$ is a deterministic CFL

  2. $L_2$ is a deterministic CFL

  3. $L_3$ is a CFL, but not a deterministic CFL

  4. $L_3$ is a deterministic CFL

asked in Theory of Computation by Veteran (59.4k points)
retagged by | 856 views

2 Answers

+13 votes
Best answer
answered by Boss (19.6k points)
edited by
0
What is class of L3?
+1
c is context sensitive language.
+1
L3 IS CSL
0
Actually sir DCFL is proper subset of CFL then option (a) is a indirectly DCFL then it can be and or not ??? Make my point clear please..
0
how is L2 DCFL ?
+7 votes

L1 : CFL
L2 : DCFL
L3 : CSL

Answer is B

answered by Active (2.3k points)
Answer:

Related questions



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

36,194 questions
43,647 answers
124,089 comments
42,930 users