The Gateway to Computer Science Excellence
+25 votes

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

in Theory of Computation by Veteran (52.2k points)
retagged by | 1.6k views

3 Answers

+17 votes
Best answer
by Boss (19.9k points)
edited by
What is class of L3?
c is context sensitive language.
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..
how is L2 DCFL ?
The # symbol in L2 exactly tells us, from which character we need to start recognizing the reverse string. It is possible for L1. In L1, we need to do trial and error method to take different breakpoints (NPDA) to find a tree and only one of the banch/path in that tree will lead to the accepting state.L1 is CFL and L2 is DCFL.
+13 votes

L1 : CFL
L3 : CSL

Answer is B

by Active (2.8k points)
why is L3 CSL?
You don't know what length you should push . It can only done via Turing machine
+1 vote
{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.
by Active (1.7k points)

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
50,737 questions
57,321 answers
105,158 users