• retagged by
16,122 views
51 51 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

8 Answers

Best answer
31 31 votes
• edited by
22 22 votes

L1 : CFL
L2 : DCFL
L3 : CSL

Answer is B

18 18 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 . 

 

3 3 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.
2 2 votes

We are given three languages over the alphabet $ \{0,1\} $, with a delimiter symbol $ \# \notin \{0,1\} $:

  • $ L_1 = \{ w w^R \mid w \in \{0,1\}^* \} $
  • $ L_2 = \{ w \# w^R \mid w \in \{0,1\}^* \} $
  • $ L_3 = \{ w w \mid w \in \{0,1\}^* \} $

Language $ L_1 $:  

$ L_1 $ is the set of even-length palindromes. It is context-free, as shown by the grammar
$$
S \to 0S0 \mid 1S1 \mid \varepsilon.
$$
However, it is not deterministic. A deterministic pushdown automaton (DPDA) cannot identify the middle of the input without a marker and must guess when to switch from pushing to popping. Since this guess cannot be made deterministically, $ L_1 \notin \text{DCFL} $. Thus,
$$
L_1 \in \text{CFL} \setminus \text{DCFL}.
$$

Language $ L_2 $:  

The symbol $ \# $ marks the center of the string. A DPDA can deterministically push symbols onto the stack while reading $ w $, and upon reading $ \# $, switch to popping mode to match $ w^R $. This yields a DPDA for $ L_2 $, so $ L_2 \in \text{DCFL} $. A context-free grammar is:
$$
S \to 0S0 \mid 1S1 \mid \#.
$$

Language $ L_3 $:  

Assume $ L_3 $ is context-free. Let $ p $ be the pumping length. Consider
$$
s = 0^p 1 0^p 1 \in L_3,
$$
where $ w = 0^p 1 $. By the pumping lemma for context-free languages, $ s = uvxyz $ with $ |vxy| \leq p $, $ |vy| \geq 1 $, and $ uv^i x y^i z \in L_3 $ for all $ i \geq 0 $.

Since $ |vxy| \leq p $, the substring $ vxy $ lies entirely within the first $ 0^p $, or spans $ 0^p 1 $, or lies in the second $ 0^p $. In every case, pumping (e.g., with $ i = 0 $) yields a string not of the form $ ww $, contradicting the assumption. Hence,
$$
L_3 \notin \text{CFL}.
$$


$$
\begin{array}{c|c}
\text{Language} & \text{Class} \\
\hline
L_1 & \text{CFL} \setminus \text{DCFL} \\
L_2 & \text{DCFL} \\
L_3 & \text{Not CFL} \\
\end{array}
$$

$$
\color{lime} \boxed{\text{Answer: B}}
$$

1 flag:
✌ (js__ “ai generated answer”)
1 1 vote

Given: L1 = {wwR | w ∈ {0,1}*}
→ Given L1 is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L2 = {w#wR | w ∈ (0,1)*}
→ Given L2 is CFL and also DCFL.
→ The string w and wR are separated by special symbol '#'.
→ L3 = {ww | w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L2 is DCFL. (✔️)

Answer:
Position:
Show:

Related questions

32 32 votes
3 answers 3 answers
15.4k
15.4k views
gatecse asked Sep 21, 2014
15,440 views
Let $f(x)$ be the continuous probability density function of a random variable $x$, the probability that $a < x \leq b$, is :$f(b-a)$$f(b) - f(a)$$\int\limits_a^b f(x) dx...
198 198 votes
9 answers 9 answers
78.6k
78.6k views
Kathleen asked Sep 22, 2014
78,561 views
A $5$ stage pipelined CPU has the following sequence of stages:IF – instruction fetch from instruction memoryRD – Instruction decode and register readEX – Execute: ALU op...
50 50 votes
6 answers 6 answers
14.6k
14.6k views
Kathleen asked Sep 22, 2014
14,589 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 compute...
34 34 votes
3 answers 3 answers
9.1k
9.1k views
Kathleen asked Sep 22, 2014
9,063 views
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...