1.6k 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.6k 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