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 proof
0
votes
1
answer
1
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
(
39.6k
points)

28
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
1
answer
2
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
(
39.6k
points)

21
views
michaelsipser
theoryofcomputation
contextfreelanguages
cnf
proof
0
votes
1
answer
3
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
(
39.6k
points)

44
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
1
answer
4
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
(
39.6k
points)

25
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
+1
vote
1
answer
5
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
(
39.6k
points)

19
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
0
answers
6
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
(
39.6k
points)

11
views
michaelsipser
theoryofcomputation
contextfreelanguages
suffixoperation
proof
0
votes
0
answers
7
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
(
39.6k
points)

13
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
8
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
(
39.6k
points)

16
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 1 Question 73 (Page No. 93)
Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

11
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
descriptive
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $s < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $s < k1k2.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{www\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

28
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that $A_{\frac{1}{2}\frac{1}{3}}=\{\text{xzfor some y,x=y=z and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}\frac{1}{3}}$ is not necessarily regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

3
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}}=\{\text{xfor some y,x=y and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

13
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation of a ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

20
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 1 Question 55 (Page No. 91)
The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length for language $A,$ so is any length $p^{'}\geq p.$ The minimum pumping ... $\epsilon$ $1^{*}01^{*}01^{*}$ $10(11^{*}0)^{*}0$ $1011$ $\sum^{*}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

4
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
20
Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$ Show that $F$ is not regular. Show that $F$ acts like a regular language in the pumping lemma. ... three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

14
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+zx,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 1 Question 52 (Page No. 91)
$\text{MyhillNerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are ... $\text{DFA}$ recognizing it$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
finiteautomata
proof
descriptive
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 1 Question 51 (Page No. 90)
Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ ... $≡L$ is an equivalence relation. A $\text{palindrome}$ is a string that reads the same forward and backward.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 1 Question 50 (Page No. 90)
Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and output alphabets are $\{0,1\}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
finitestatetransducer
proof
descriptive
0
votes
1
answer
25
Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

17
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
Let $\sum = \{0,1\}$ and let $D = \{ww$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$ Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{ww=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}m,n\geq 0\}$ $\{0^{m}1^{n}m\neq n\}$ $\{ww\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtww,t\in\{0,1\}^{+}\}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROPOUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROPOUT(A) = $\{xz xyz\in A$ where $x, ... $\text{Theorem 1.47.}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 39 (Page No. 89)
The construction in $\text{Theorem 1.54}$ shows that every $\text{GNFA}$ is equivalent to a $\text{GNFA}$ with only two states$.$ We can show that an opposite phenomenon occurs for $\text{DFAs.}$ Prove that for every $k > 1,$ a ... exists that is recognized by a $\text{DFA}$ with $k$ states but not by one with only $k − 1$ states$.$
asked
Apr 28
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.6k
points)

19
views
michaelsipser
theoryofcomputation
finiteautomata
dfanfa
proof
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
Follow @csegate
Recent questions tagged proof
Recent Blog Comments
a heartiest congratulations mam :)
Congratulations
Thank you
Very Nice. Congratulations ))👍
Congratulations 👍 Very nice experience 😊
49,541
questions
54,080
answers
187,200
comments
70,990
users