The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.4k 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
asked in Theory of Computation by Veteran (96.1k points)
edited by | 1.4k views
0

L3 is Non deterministic CFL ...

2 Answers

+26 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. 

answered by Boss (19.9k points)
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.
0
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.

answered by Active (1.9k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,083 answers
187,207 comments
70,992 users