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
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
0
answers
2
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} contextfree?
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14.9k
points)

38
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
1
answer
3
Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not contextfree.
asked
Jun 25
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14.9k
points)

45
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
4
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
Veteran
(
50.8k
points)

46
views
michaelsipser
theoryofcomputation
contextfreelanguages
pumpinglemma
0
votes
1
answer
5
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
6
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
1
answer
7
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
Veteran
(
50.8k
points)

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

52
views
michaelsipser
theoryofcomputation
finiteautomata
pumpinglemma
proof
0
votes
1
answer
11
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
Veteran
(
50.8k
points)

77
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
0
votes
1
answer
12
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
(
115k
points)

50
views
theoryofcomputation
pumpinglemma
0
votes
0
answers
13
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
(
11.2k
points)

41
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
14
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
(
11.2k
points)

40
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
15
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
(
11.2k
points)

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
16
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
(
11.2k
points)

25
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
17
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
(
11.2k
points)

7
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
18
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
(
11.2k
points)

27
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
19
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
(
11.2k
points)

16
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
20
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
(
11.2k
points)

6
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
21
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
(
11.2k
points)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
22
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
(
11.2k
points)

21
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
23
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
(
11.2k
points)

26
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
24
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
(
11.2k
points)

23
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguage
0
votes
0
answers
25
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
(
11.2k
points)

13
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguage
0
votes
0
answers
26
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
(
11.2k
points)

19
views
peterlinz
theoryofcomputation
proof
pumpinglemma
0
votes
0
answers
27
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
(
11.2k
points)

25
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
28
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
(
11.2k
points)

4
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
29
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
(
11.2k
points)

3
views
peterlinz
theoryofcomputation
pumpinglemma
proof
0
votes
0
answers
30
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
(
14.9k
points)

35
views
peterlinz
theoryofcomputation
regularlanguages
pumpinglemma
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
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 pumpinglemma
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,101
users