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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged contextfreelanguages
0
votes
0
answers
1
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
+1
vote
1
answer
2
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

8
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
3
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
4
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
5
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
6
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreelanguages
closureproperty
descriptive
0
votes
0
answers
7
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
8
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
9
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
10
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
11
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
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
0
answers
12
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
3 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

15
views
michaelsipser
theoryofcomputation
contextfreelanguages
prefixclosed
0
votes
0
answers
13
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
3 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreelanguages
shuffle
0
votes
0
answers
14
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
3 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

3
views
michaelsipser
theoryofcomputation
contextfreelanguages
perfectshuffle
0
votes
0
answers
15
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
(
14.9k
points)

21
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
16
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
(
14.9k
points)

14
views
peterlinz
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
0
answers
17
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
(
14.9k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
18
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
(
14.9k
points)

6
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
19
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
(
14.9k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
20
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
(
14.9k
points)

6
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
21
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
(
14.9k
points)

7
views
peterlinz
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
22
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
(
14.9k
points)

36
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
23
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
(
14.9k
points)

14
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
24
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
(
14.9k
points)

16
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
25
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
(
14.9k
points)

7
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
26
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
(
14.9k
points)

10
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
27
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
(
14.9k
points)

16
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
1
answer
28
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
(
14.9k
points)

31
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
29
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
(
14.9k
points)

18
views
peterlinz
theoryofcomputation
contextfreelanguages
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 7.3 Question 7 (Page No. 200)
Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k$}.
asked
Jun 23
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14.9k
points)

27
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
Standard Videos for Calculus
Standard Videos for Linear Algebra
Standard Videos for Graph Theory
Standard Videos for Combinatory
Standard Videos for Set Theory & Algebra
Follow @csegate
Recent questions tagged contextfreelanguages
Recent Blog Comments
I will add the videos link soon.
video link ?
I think no need to add GO classroom content...
For combinatorics , can add balls and bin...
Yes, and it is really helpful for us. Thanks
50,288
questions
55,716
answers
192,103
comments
90,099
users