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 pumpinglemma
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
(
39.8k
points)

35
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
(
39.8k
points)

28
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
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.8k
points)

45
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
0
votes
0
answers
4
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
(
39.8k
points)

9
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
0
votes
0
answers
5
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.8k
points)

4
views
michaelsipser
theoryofcomputation
regularlanguages
pumpinglemma
proof
descriptive
0
votes
1
answer
6
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.8k
points)

17
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 1 Question 30 (Page No. 88)
Describe the error in the following $ $proof$"$ that $0^{*}1^{*}$ is not a regular language. $($An error must exist because $0^{*}1^{*}$ is regular.$)$ The proof is by contradiction. Assume that $0^{*}1^{*}$ is regular ... example $1.73$ shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.
asked
Apr 22
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.8k
points)

40
views
michaelsipser
theoryofcomputation
finiteautomata
pumpinglemma
proof
0
votes
1
answer
8
Michael Sipser Edition 3 Exercise 1 Question 29 (Page No. 88)
Use the pumping lemma to show that the following languages are not regular. $A_{1}=\{0^{n}1^{n}2^{n}n\geq 0\}$ $A_{2}=\{wwww\in\{a,b\}^{*}\}$ $A_{3}=\{a^{{2}^{n}}n\geq 0\}$ $\text{(Here,}$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$
asked
Apr 22
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.8k
points)

55
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
0
votes
1
answer
9
Self doubt:Pumping Lemma
How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ?
asked
Apr 19
in
Theory of Computation
by
srestha
Veteran
(
111k
points)

38
views
theoryofcomputation
pumpinglemma
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

32
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

37
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree $L = \{a^nb^m: \text{n and m are both prime}\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

19
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

24
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

6
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

13
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

13
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L=\{a^nb^jc^k : k>n,k>j\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

5
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^jc^k:k=jn\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^j: n\geq(j1)^3\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

20
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not contextfree. $L = \{a^nb^j : n\leq j^2\}$.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

26
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

12
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 8.1 Question 4 (Page No. 212)
Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a contextfree.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

18
views
peterlinz
theoryofcomputation
proof
pumpinglemma
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 8.1 Question 3 (Page No. 212)
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a contextfree language.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 8.1 Question 2 (Page No. 212)
Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not contextfree.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

3
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$ is not contextfree.
asked
Apr 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

3
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 4.3 Question 26 (Page No. 124)
Let $L=$ {$a^nb^m:n\geq100,m\leq50$}. (a) Can you use the pumping lemma to show that L is regular? (b) Can you use the pumping lemma to show that L is not regular? Explain your answers.
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

29
views
peterlinz
theoryofcomputation
regularlanguages
pumpinglemma
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 4.3 Question 16 (Page No. 123)
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

14
views
peterlinz
theoryofcomputation
pumpinglemma
regularlanguages
closureproperty
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 4.3 Question 15 (Page No. 123)
Consider the languages below. For each, make a conjecture whether or not it is regular. Then prove your conjecture. (a) $L=$ {$a^nb^la^k:n+k+l \gt 5$} (b) $L=$ {$a^nb^la^k:n \gt 5,l> 3,k\leq l$} (c) $L=$ {$a^nb^l:n/l$ is an integer} (d) $L=$ ... $L=$ {$a^nb^l:n\geq 100,l\leq 100$} (g) $L=$ {$a^nb^l:nl=2$}
asked
Apr 12
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

29
views
peterlinz
theoryofcomputation
regularlanguages
pumpinglemma
closureproperty
0
votes
1
answer
30
Peter Linz Edition 4 Exercise 4.3 Question 13 (Page No. 123)
Show that the following language is not regular. $L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k1$}.
asked
Apr 11
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

46
views
peterlinz
theoryofcomputation
pumpinglemma
regularlanguages
closureproperty
Page:
1
2
3
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
IIITH Interview Experience
Thanks GO!!
IIIT Hyerabad Interview Expeience  MS by Research in CSE
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
Follow @csegate
Recent questions tagged pumpinglemma
Recent Blog Comments
Congratulations :)
Congratulations 😊 👍
Thank you bro @Shaik
Thank you Sir.
congratulations :)
49,532
questions
54,123
answers
187,319
comments
71,044
users