Register

Recent questions tagged pumping-lemma

397
views
0 answers
0 votes
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}\}$.
User Avatar
369
views
1 answers
0 votes
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}\}$.
User Avatar
204
views
0 answers
0 votes
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}\}$.
User Avatar
316
views
0 answers
0 votes
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)\}$.
User Avatar
192
views
0 answers
0 votes
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)\}$.
User Avatar
240
views
0 answers
0 votes
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)\}$.
User Avatar
306
views
0 answers
0 votes
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\}$.
User Avatar
207
views
0 answers
0 votes
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\}$.
User Avatar
597
views
2 answers
0 votes
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\}$.
User Avatar
155
views
0 answers
0 votes
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\}$.
User Avatar
302
views
0 answers
1 votes
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\}$.
User Avatar
351
views
0 answers
0 votes
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.
User Avatar
248
views
0 answers
0 votes
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
User Avatar
162
views
0 answers
0 votes
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.
User Avatar
205
views
0 answers
0 votes
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.
User Avatar
155
views
0 answers
0 votes
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.
User Avatar
169
views
0 answers
0 votes
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.
User Avatar
266
views
0 answers
0 votes
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.
User Avatar
341
views
1 answers
1 votes
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$}.
User Avatar
336
views
0 answers
1 votes
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. Thenprove your conjecture.(a) $L=$ {$a^nb^la^k:n+k+l \gt 5$}(b) $L=$ ... {$a^nb^l:n\geq 100,l\leq 100$}(g) $L=$ {$a^nb^l:|n-l|=2$}
User Avatar
299
views
1 answers
0 votes
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$}.
User Avatar
473
views
1 answers
0 votes
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$ isalso non regular.
User Avatar
318
views
1 answers
0 votes
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.
User Avatar
257
views
0 answers
2 votes
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.
User Avatar
311
views
1 answers
0 votes
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?
User Avatar
310
views
1 answers
0 votes
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.
User Avatar
167
views
0 answers
1 votes
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.
User Avatar
403
views
0 answers
1 votes
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 ... of two or more prime numbers}.(g) $L^*$, where $L$ is the language in part $(a)$.
User Avatar
237
views
0 answers
0 votes
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) ... $ww : w ∈${$a, b$}$^*$}.(g) $L =$ {$wwww^R : w ∈$ {$a, b$}$^*$}.
User Avatar
369
views
1 answers
0 votes
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?
User Avatar
Page: