Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged pumping-lemma
0
votes
0
answers
31
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 context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not ...
Rishi yadav
347
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
1
answer
32
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 context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prim...
Rishi yadav
334
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
33
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 context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prim...
Rishi yadav
188
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
34
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 context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\...
Rishi yadav
288
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
35
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 context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w...
Rishi yadav
166
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
36
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 context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $$L = \{w:n_a(w) <n_b(w)<n_c(w)\}$$.
Rishi yadav
206
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
37
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 context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$...
Rishi yadav
271
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
38
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 context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.
Rishi yadav
181
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
2
answers
39
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 context-free. $L = \{a^nb^jc^k:k=jn\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\...
Rishi yadav
450
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
40
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 context-free. $L = \{a^nb^j: n\geq(j-1)^3\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-...
Rishi yadav
140
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
1
votes
0
answers
41
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 context-free. $L = \{a^nb^j : n\leq j^2\}$.
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}...
Rishi yadav
275
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
42
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.
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
Rishi yadav
297
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
+
–
0
votes
0
answers
43
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
Rishi yadav
237
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
0
answers
44
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 context-free.
Show that $L=\{w \in \{a,b,c\}^*:n_a^2(w) + n_b^2(w) = n_c^2(w)\}$ is not a context-free.
Rishi yadav
142
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
pumping-lemma
+
–
0
votes
0
answers
45
Peter Linz Edition 5 Exercise 8.1 Question 3 (Page No. 212)
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.
Show that $L=\{ww^Rw:w\in\{a,b\}^*\}$ is not a context-free language.
Rishi yadav
173
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
0
votes
0
answers
46
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 context-free.
Show that the language $L = \{a^n : n \text{ is a prime number}\}$ is not context-free.
Rishi yadav
125
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
0
votes
0
answers
47
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 context-free.
Show that the language $L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}$is not context-free.
Rishi yadav
140
views
Rishi yadav
asked
Apr 15, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
+
–
0
votes
0
answers
48
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.
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 y...
Naveen Kumar 3
219
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
1
votes
1
answer
49
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$}.
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
Naveen Kumar 3
296
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
1
votes
0
answers
50
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:|n-l|=2$}
Consider the languages below. For each, make a conjecture whether or not it is regular. Thenprove your conjecture.(a) $L=$ {$a^nb^la^k:n+k+l \gt 5$}(b) $L=$ {$a^nb^la^k:n...
Naveen Kumar 3
302
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
closure-property
+
–
0
votes
1
answer
51
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 k-1$}.
Show that the following language is not regular.$L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
Naveen Kumar 3
277
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
0
votes
1
answer
52
Peter Linz Edition 4 Exercise 4.3 Question 14 (Page No. 123)
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ is also non regular.
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ isalso non regular.
Naveen Kumar 3
377
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
0
votes
1
answer
53
Peter Linz Edition 4 Exercise 4.3 Question 12 (Page No. 123)
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Naveen Kumar 3
242
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
2
votes
0
answers
54
Peter Linz Edition 4 Exercise 4.3 Question 10 (Page No. 123)
Consider the language $L=$ {$a^n:n$ is not a perfect square}. (a) Show that this language is not regular by applying the pumping lemma directly. (b) Then show the same thing by using the closure properties of regular languages.
Consider the language $L=$ {$a^n:n$ is not a perfect square}.(a) Show that this language is not regular by applying the pumping lemma directly.(b) Then show the same thin...
Naveen Kumar 3
240
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
0
votes
1
answer
55
Peter Linz Edition 4 Exercise 4.3 Question 9 (Page No. 123)
Is the language $L=$ {$w∈$ {$a,b,c$}$^*$ $:|w|=3n_a(w)$} regular?
Is the language $L=$ {$w∈$ {$a,b,c$}$^*$ $:|w|=3n_a(w)$} regular?
Naveen Kumar 3
280
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
1
answer
56
Peter Linz Edition 4 Exercise 4.3 Question 8 (Page No. 123)
Show that the language $L=$ {$a^nb^{n+k}:n\geq0,k\geq1$} $\cup$ {$a^{n+k}b^n:n\geq0,k\geq3$} is not regular.
Show that the language $L=$ {$a^nb^{n+k}:n\geq0,k\geq1$} $\cup$ {$a^{n+k}b^n:n\geq0,k\geq3$} is not regular.
Naveen Kumar 3
281
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
1
votes
0
answers
57
Peter Linz Edition 4 Exercise 4.3 Question 7 (Page No. 123)
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
1
votes
0
answers
58
Peter Linz Edition 4 Exercise 4.3 Question 5 (Page No. 122)
Determine whether or not the following languages on $Σ =$ {$a$} are regular. (a) $L =$ {$a^n: n ≥ 2,$ is a prime number}. (b) $L =$ {$a^n: n$ is not a prime number}. (c) $L =$ {$a^n: n = k^3$ for some $k ≥ 0$}. ( ... {$a^n: n$ is either prime or the product of two or more prime numbers}. (g) $L^*$, where $L$ is the language in part $(a)$.
Determine whether or not the following languages on $Σ =$ {$a$} are regular.(a) $L =$ {$a^n: n ≥ 2,$ is a prime number}.(b) $L =$ {$a^n: n$ is not a prime number}.(c) ...
Naveen Kumar 3
347
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
59
Peter Linz Edition 4 Exercise 4.3 Question 4 (Page No. 122)
Prove that the following languages are not regular. (a) $L =$ {$a^nb^la^k : k ≥ n + l$}. (b) $L =$ {$a^nb^la^k : k ≠ n + l$}. (c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}. (d) $L =$ {$a^nb^l : n ≤ l$}. (e) $L =$ {$w: n_a (w) ≠ n_b (w)$ }. (f) $L =$ {$ww : w ∈${$a, b$}$^*$}. (g) $L =$ {$wwww^R : w ∈$ {$a, b$}$^*$}.
Prove that the following languages are not regular.(a) $L =$ {$a^nb^la^k : k ≥ n + l$}.(b) $L =$ {$a^nb^la^k : k ≠ n + l$}.(c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}...
Naveen Kumar 3
217
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
1
answer
60
Peter Linz Edition 4 Exercise 4.3 Question 3 (Page No. 122)
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Show that the language $L = \{w : n_a (w) = n_b(w) \}$ is not regular. Is $L^*$ regular?
Naveen Kumar 3
326
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
Page:
« prev
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register