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
0
answers
1
Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)
Show that every DCFG generates a prefixfree language.
asked
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

2
views
michaelsipser
theoryofcomputation
contextfreegrammars
prefixfreelanguage
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 2 Question 51 (Page No. 159)
Show that every DCFG is an unambiguous CFG.
asked
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

1
view
michaelsipser
theoryofcomputation
contextfreegrammars
ambiguous
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.
asked
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

4
views
michaelsipser
theoryofcomputation
contextfreegrammars
ambiguous
proof
0
votes
0
answers
4
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
5
Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.
asked
1 day
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.8k
points)

3
views
michaelsipser
theoryofcomputation
regularlanguages
proof
0
votes
0
answers
6
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
7
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
8
Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are contextfree. (a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*} (b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}. (C) $L=$ {$a^nb^ja^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14.9k
points)

59
views
peterlinz
theoryofcomputation
contextfreelanguage
pumpinglemma
proof
0
votes
1
answer
9
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
Veteran
(
50.8k
points)

53
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
1
answer
10
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
Veteran
(
50.8k
points)

29
views
michaelsipser
theoryofcomputation
contextfreelanguages
cnf
proof
0
votes
1
answer
11
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
Veteran
(
50.8k
points)

65
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
2
answers
12
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
Veteran
(
50.8k
points)

50
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
+1
vote
1
answer
13
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
Veteran
(
50.8k
points)

25
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
0
answers
14
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
Veteran
(
50.8k
points)

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
suffixoperation
proof
0
votes
1
answer
15
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
Veteran
(
50.8k
points)

22
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
16
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
Veteran
(
50.8k
points)

21
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
17
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
Veteran
(
50.8k
points)

15
views
michaelsipser
theoryofcomputation
contextfreelanguages
proof
descriptive
0
votes
0
answers
18
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
Veteran
(
50.8k
points)

48
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
19
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
Veteran
(
50.8k
points)

29
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
20
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
Veteran
(
50.8k
points)

21
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
21
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
Veteran
(
50.8k
points)

18
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
22
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
Veteran
(
50.8k
points)

35
views
michaelsipser
theoryofcomputation
regularlanguages
scarnescut
proof
descriptive
0
votes
0
answers
23
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
Veteran
(
50.8k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
0
answers
24
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
Veteran
(
50.8k
points)

7
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
25
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
Veteran
(
50.8k
points)

19
views
michaelsipser
theoryofcomputation
regularlanguages
proof
descriptive
0
votes
0
answers
26
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
Veteran
(
50.8k
points)

27
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
27
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
Veteran
(
50.8k
points)

33
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
28
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
Veteran
(
50.8k
points)

45
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
29
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
Veteran
(
50.8k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
30
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
Veteran
(
50.8k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
finiteautomata
proof
descriptive
Page:
1
2
3
4
5
6
7
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 proof
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,102
comments
90,096
users