The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1k 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.7k points)
retagged by | 1k views

3 Answers

+14 votes
Best answer
answered by Boss (19.9k 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 ?
+8 votes

L1 : CFL
L2 : DCFL
L3 : CSL

Answer is B

answered by Active (2.5k points)
0
why is L3 CSL?
0
You don't know what length you should push . It can only done via Turing machine
0 votes
{wwR,  where w is a string of a and b} is non deteministic CFL because till half of the length, we have to push and then we have to pop. but we dont know length. So at each step, we will push the next symbol and pop the previous one to see which one works. so it is non deteminsitic. So a CFL will be either deterministic or non deterministic but in case by w#wR we know that at # we have to stop pushing and after # we start popping hence it is DPDA.
answered by Junior (903 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

44,200 questions
49,671 answers
163,565 comments
65,819 users