retagged by
8,370 views
36 votes
36 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

retagged by

5 Answers

Best answer
28 votes
28 votes
edited by
19 votes
19 votes

L1 : CFL
L2 : DCFL
L3 : CSL

Answer is B

6 votes
6 votes

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 . 

 

2 votes
2 votes
{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.
Answer:

Related questions

26 votes
26 votes
3 answers
4