The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged contextfreelanguages
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 4 Question 31 (Page No. 212)
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 2 Question 58 (Page No. 160)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its ... of $P's$ stack at that point cannot affect its subsequent behavior, so $P's$ subsequent behavior can depend only on $q$ and $x$.)
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
+2
votes
1
answer
3
Michael Sipser Edition 3 Exercise 2 Question 57 (Page No. 160)
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 2 Question 56 (Page No. 160)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ ... an accept state, it pretends that $c's$ are $b's$ in the input from that point on. What language would the modified $P$ accept?)
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 2 Question 53 (Page No. 159)
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

6
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 2 Question 50 (Page No. 159)
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 2 Question 49 (Page No. 159)
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 2 Question 48 (Page No. 159)
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $1s$ ... $C_{1}$ is a CFL. Show that $C_{2}$ is not a CFL.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

6
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
asked
Oct 12
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 2 Question 43 (Page No. 158)
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ ... a regular language is context free. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.
asked
Oct 12
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
asked
Oct 12
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

3
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 2 Question 41 (Page No. 158)
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$. Show that the class of CFLs is not closed under NOPREFIX. Show that the class of CFLs is not closed under NOEXTEND.
asked
Oct 12
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

6
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 2 Question 40 (Page No. 158)
Say that a language is prefixclosed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefixclosed, contextfree language. Show that $C$ contains an infinite regular subset.
asked
Oct 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

25
views
michaelsipser
theoryofcomputation
contextfreelanguages
prefixclosed
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 2 Question 39 (Page No. 158)
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of contextfree languages is not closed under shuffle.
asked
Oct 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
michaelsipser
theoryofcomputation
contextfreelanguages
shuffle
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 2 Question 38 (Page No. 158)
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ... k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of contextfree languages is not closed under perfect shuffle.
asked
Oct 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
michaelsipser
theoryofcomputation
contextfreelanguages
perfectshuffle
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

30
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 7.4 Question 7 (Page No. 204)
Show that a deterministic contextfree language is never inherently ambiguous.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

17
views
peterlinz
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic contextfree language.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

9
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
20
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

9
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
22
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

14
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 7.3 Question 18 (Page No. 200)
Give an example of a deterministic contextfree language whose reverse is not deterministic.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

46
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 7.3 Question 17 (Page No. 200)
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic contextfree language.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

16
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
25
Peter Linz Edition 4 Exercise 7.3 Question 16 (Page No. 200)
Show that if $L_1$ is deterministic contextfree and $L_2$ is regular, then the language $L_1 ∪ L_2$ is deterministic contextfree.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

19
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
26
Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic contextfree language.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

15
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 7.3 Question 11 (Page No. 200)
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic contextfree language.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

12
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
28
Peter Linz Edition 4 Exercise 7.3 Question 10 (Page No. 200)
While the language in Exercise 9 is deterministic, the closely related language $L =$ {$ww^R : w ∈${$a,b$}$^*$} is known to be nondeterministic. Give arguments that make this statement plausible.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

19
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
29
Peter Linz Edition 4 Exercise 7.3 Question 9 (Page No. 200)
Is the language {$wcw^R : w ∈ ${$a, b$}$^*$} deterministic?
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

35
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 7.3 Question 8 (Page No. 200)
Is the language $L =$ {$a^nb^m : n = m$ or $n = m + 2$} deterministic?
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

22
views
peterlinz
theoryofcomputation
contextfreelanguages
Page:
1
2
3
4
5
6
next »
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
Recent Posts
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged contextfreelanguages
Recent Blog Comments
@`JEET No brother, I don't have. These points I...
Brother post after $\mathbf 1$ year?
Congratulations :)
Lakshman Patel RJIT Do you have such notes...
Great work sir
50,645
questions
56,565
answers
195,746
comments
101,696
users