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 michaelsipser
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 2 Question 37 (Page No. 158)
Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a contextfree language, then there is a number $k$ where, if $s$ is any string in $A$ of ... $i\geq 0,uv^{i}xy^{i}z\in A,$ $v\neq\epsilon$ and $y\neq\epsilon,$and $\mid vxy\mid\leq k.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

45
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
0
votes
1
answer
2
Michael Sipser Edition 3 Exercise 2 Question 36 (Page No. 158)
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

52
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
1
answer
3
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

28
views
michaelsipser
theoryofcomputation
contextfreelanguages
cnf
proof
0
votes
1
answer
4
Michael Sipser Edition 3 Exercise 2 Question 34 (Page No. 157)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ ... existence of a pumping length $p$ for $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

62
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
1
answer
5
Michael Sipser Edition 3 Exercise 2 Question 33 (Page No. 157)
Show that $F = \{a^{i}b^{j}\mid i = kj$ $\text{for some positive integer $k$\}}$ is not context free$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

23
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
2
answers
6
Michael Sipser Edition 3 Exercise 2 Question 32 (Page No. 157)
Let $\Sigma = \{1, 2, 3, 4\}$ and $C = \{w\in\Sigma^{*}\mid$ $\text{in $w$, the number of $1's$ equals the number of $2's,$ and the number of $3's$ equals the number of }$4's\}.$ Show that $C$ is not context free$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

46
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
1
answer
7
Michael Sipser Edition 3 Exercise 2 Question 31 (Page No. 157)
Let $B$ be the language of all palindromes over $\{0,1\}$ containing equal numbers of $0's$ and $1's.$ Show that $B$ is not context free$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

30
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
1
answer
8
Michael Sipser Edition 3 Exercise 2 Question 30 (Page No. 157)
Use the pumping lemma to show that the following languages are not context free$.$ $\{0^{n}1^{n}0^{n}1^{n}\mid n\geq 0\}$ $\{0^{n}\#0^{2n}\#0^{3n}\mid n\geq 0\}$ $\{w\#t\mid w$ $\text{ is a substring of}$ $ t,$ $\text{where}$ ... $\text{each}$ $ t_{i}\in\{a,b\}^{*},$ $\text{and}$ $ t_{i}=t_{j}$ $\text{ for some}$ $ i\neq j\}$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

30
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 2 Question 29 (Page No. 157)
Show that the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}$ is inherently ambiguous$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

19
views
michaelsipser
theoryofcomputation
contextfreelanguages
inherentlyambiguous
0
votes
1
answer
10
Michael Sipser Edition 3 Exercise 2 Question 28 (Page No. 157)
Give unambiguous $CFG's$ for the following languages$.$ $\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$ $\text{{$w\mid$ the number of $a’s$ and the number of $b’s$ in $w$ are equal}}$ $\text{{$w\mid$ the number of $a’s$ is at least the number of $b’s$ in $w$}}$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

24
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
11
Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a naturallooking grammar for a fragment of a programming language, but $G$ is ambiguous$.$ Show that $G$ is ambiguous$.$ Give a new unambiguous grammar for the same language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

25
views
michaelsipser
theoryofcomputation
contextfreegrammars
ambiguousgrammar
+1
vote
1
answer
12
Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

24
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 2 Question 25 (Page No. 157)
For any language $A,$ let $SUFFIX(A) = \{v\mid uv \in A$ $\text{for some string u\}}.$ Show that the class of contextfree languages is closed under the $\text{SUFFIX operation.}$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

21
views
michaelsipser
theoryofcomputation
contextfreelanguages
suffixoperation
proof
0
votes
1
answer
14
Michael Sipser Edition 3 Exercise 2 Question 24 (Page No. 157)
Let $E=\{a^{i}b^{j}\mid i\neq j$ $\text{and}$ $2i\neq j\}.$ Show that $E$ is a contextfree language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

21
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 2 Question 23 (Page No. 157)
Let $D = \{xy\mid x, y\in \{0,1\}^{*}$ $\text{and}$ $\mid x\mid = \mid y\mid$ $\text{but}$ $x\neq y\}.$ Show that $D$ is a contextfree language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

20
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
1
answer
16
Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a contextfree language$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

22
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
17
Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

9
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 2 Question 20 (Page No. 156)
Let $A/B = \{w\mid wx\in A$ $\text{for some}$ $x \in B\}.$ Show that if $A$ is context free and $B$ is regular$,$ then $A/B$ is context free$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

12
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$ $Y\rightarrow bY \mid aY \mid \epsilon$ Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

10
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
20
Michael Sipser Edition 3 Exercise 2 Question 18 (Page No. 156)
Let $C$ be a contextfree language and $R$ be a regular language$.$ Prove that the language $C\cap R$ is contextfree. Let $A = \{w\mid w\in \{a, b, c\}^{*}$ $\text{and}$ $w$ $\text{contains equal numbers of}$ $a’s, b’s,$ $\text{and}$ $c’s\}.$ Use $\text{part (a)}$ to show that $A$ is not a CFL$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

11
views
michaelsipser
theoryofcomputation
contextfreelanguages
regularlanguages
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 2 Question 17 (Page No. 156)
Use the results of $\text{Question 16}$ to give another proof that every regular language is context free$,$ by showing how to convert a regular expression directly to an equivalent contextfree grammar$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

10
views
michaelsipser
theoryofcomputation
regularlanguages
contextfreelanguages
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 2 Question 16 (Page No. 156)
Show that the class of contextfree languages is closed under the regular operations$,$ union$,$ concatenation, and star$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

10
views
michaelsipser
theoryofcomputation
contextfreelanguages
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 2 Question 15 (Page No. 156)
Give a counterexample to show that the following construction fails to prove that the class of contextfree languages is closed under star. Let $A$ be a $\text{CFL}$ that is generated by the $\text{CFG}$ ... new rule $S\rightarrow SS$ and call the resulting grammar $G'.$This grammar is supposed to generate $A^{*}.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

12
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
1
answer
24
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

21
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
0
votes
1
answer
25
Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$
asked
May 4
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

25
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
Convert the $CFG$ $G$ $R\rightarrow XRX \mid S$ $S\rightarrow aT b \mid bT a$ $T\rightarrow XT X \mid X \mid\epsilon$ $X\rightarrow a \mid b$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
asked
May 2
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

26
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 2 Question 11 (Page No. 155)
Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$ $T\rightarrow T\times F\mid F$ $F\rightarrow (E)\mid a$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)
Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

25
views
michaelsipser
theoryofcomputation
contextfreelanguages
pushdownautomata
0
votes
1
answer
29
Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)
Give a contextfree grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why or why not$?$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

14
views
michaelsipser
theoryofcomputation
contextfreelanguages
ambiguous
grammars
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 2 Question 8 (Page No. 155)
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_2$ on $\text{page 103.} $ Describe in English the two different meanings of this sentence.
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
47.5k
points)

9
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
Page:
1
2
3
4
5
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
Previous Years Question Papers : ISI  MMA, PCB, DCG
Previous Years Question Papers : CMI  Computer Science
Minimum Number of States in a DFA accepting a binary number divisible by 'n'
GATE 2020 Application Form Opened!
My GATE Preparation Journey
Follow @csegate
Recent questions tagged michaelsipser
Recent Blog Comments
Feedback for next edition (if ever there's...
Is go book still available,I want to buy it
will pdfs be uploaded ?
50,092
questions
55,291
answers
190,810
comments
86,116
users