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

retagged | 1k views

(B) is TRUE.

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 ?

L1 : CFL
L2 : DCFL
L3 : CSL

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.

1
2