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
Recent questions tagged pumpinglemma
+1
vote
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

82
views
peterlinz
theoryofcomputation
contextfreelanguages
pumpinglemma
proof
+2
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

54
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

56
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

54
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

79
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

81
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

38
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

55
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

51
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

54
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
58.7k
points)

83
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, 2019
in
Theory of Computation
by
srestha
Veteran
(
119k
points)

67
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

46
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

43
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

24
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

29
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

9
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

30
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

19
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

8
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

25
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

22
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
+1
vote
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

31
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

26
views
peterlinz
theoryofcomputation
pumpinglemma
proof
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

14
views
peterlinz
theoryofcomputation
pumpinglemma
contextfreelanguages
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
points)

26
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
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, 2019
in
Theory of Computation
by
Rishi yadav
Boss
(
11.6k
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

36
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged pumpinglemma
Recent Blog Comments
I guess the answer to this will be software...
@Susheel It will be 1250 only,because when you...
In set A, Little endian question answer given...
What about this...
Compared to previous years...was this paper...
50,737
questions
57,279
answers
198,173
comments
104,840
users