search
Log In
22 votes
2.7k views

Consider the following languages over the alphabet $\sum = \{0, 1, c\}$

$L_1  = \left\{0^n1^n\mid n \geq 0\right\}$

$L_2 = \left\{wcw^r \mid w \in \{0,1\}^*\right\}$

$L_3 = \left\{ww^r \mid w \in \{0,1\}^*\right\}$

Here, $w^r$ is the reverse of the string $w$. Which of these languages are deterministic Context-free languages?

  1. None of the languages
  2. Only $L_1$
  3. Only $L_1$ and $L_2$
  4. All the three languages
in Theory of Computation
edited by
2.7k views
0

L3 is Non deterministic CFL ...

3 Answers

33 votes
 
Best answer

C.

$L_3$  is CFL and not DCFL as in no way we can deterministically determine the MIDDLE point of the input string. 


edited by
0
Should not the answer be B? Because c belongs to the input alphabet.
0

As c belongs to the input alphabet, it is used to determine the middle part of the string.
for example 110c011 is in the language L2. every element is pushed to the stack untill a c occurs. Then the pda changes state and the popping starts.

0
Oh yea. Sorry. I mistook c to be a part of w as well.
1
If your push and pop is clear then it  is deterministic context free language otherwise not.
2 votes

For the languages L& L  we can have deterministic push down automata, so they are
DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a
deterministic CFL.

0 votes
L1 and L2 are deterministic CFL, as we can design DPDA for them.

But in L3, we cannot make DPDA for it, as we cannot locate the middle of the string, so DPDA for L3 is not possible. It can be accepted by only NPDA, so L3 is CFL but not DCFL.
Answer:

Related questions

24 votes
3 answers
1
2.9k views
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.
asked Sep 28, 2014 in Theory of Computation jothee 2.9k views
31 votes
10 answers
2
7.2k views
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only
asked Feb 14, 2018 in Theory of Computation gatecse 7.2k views
36 votes
8 answers
3
4.9k views
Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ $G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon$ The language $L\left ( G_{1} \right )\cap L(G_{2})$ is Finite Not finite but regular Context-Free but not regular Recursive but not context-free
asked Feb 14, 2017 in Theory of Computation Arjun 4.9k views
28 votes
2 answers
4
4.8k views
Consider the languages $L1=\{0^i1^j\ \mid i \neq j\}, $ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$ Only $L2$ is context free. Only $L2$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free
asked Sep 30, 2014 in Theory of Computation jothee 4.8k views
...