# GATE2005-57

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

(B) is TRUE.

edited by
0
What is class of L3?
1
c is context sensitive language.
2
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

0
why is L3 CSL?
0
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.

L1 is a Non Deterministic CFL as we can make a automata using a stack. We can push the string (w) in a stack and when two elements are same consecutively and we have two cases -

- It might be the starting of reverse of w.  Say abba then w=ab , and when we get second b it is the starting of reverse string .

- It might just be a part of w . Say  bbaabb Here second b is just a part of w.

So this PDA is non deterministic .

L2 is a Deterministic CFL . We can push the string (w) in a stack and we know as soon as we encounter # that's the beginning of reverse of w. And hence can represent it using a push down automata .

L3 is a context sensitive language as it can't be represented using a Push Down Automata as there is significance about when w ends and start again .

## Related questions

1
2.9k views
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is TRUE? It computes $1$’s complement of the input number It computes $2$’s complement of the input number It increments the input number it decrements the input number
Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? $L_1$' is recursive and $L_2$' is recursively enumerable $L_1$' is recursive and $L_2$' is not recursively enumerable $L_1$' and $L_2$' are recursively enumerable $L_1$' is recursively enumerable and $L_2$' is recursive
Let $N_f$ and $N_p$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $D_f$ and $D_p$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one ... $D_f = N_f \text{ and } D_p = N_p$ $D_f =N_f \text{ and } D_p \subset N_p$
Consider a relation scheme $R = (A, B, C, D, E, H)$ on which the following functional dependencies hold: {$A \rightarrow B$, $BC \rightarrow D$, $E \rightarrow C$, $D \rightarrow A$}. What are the candidate keys R? $AE, BE$ $AE, BE, DE$ $AEH, BEH, BCH$ $AEH, BEH, DEH$