1.3k 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

retagged | 1.3k views

(B) is TRUE.

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 ?
0
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.

L1 : CFL
L2 : DCFL
L3 : CSL

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

1
2