# Recent questions tagged pumping-lemma

1 vote
1 answer
1
The logic of pumping lemma is a good example of the pigeon-hole principle the divide and conquer technique recursion iteration
1 vote
0 answers
2
Determine whether or not the following languages are context-free. (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$}. (e)$L=$ {$a^nb^ja^kb^l : n ≤ k, j ≤ l$}. (f) $L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
2 votes
0 answers
3
Is the language L = {$a^nb^m : n = 2^m$} context-free?
0 votes
1 answer
4
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
0 votes
0 answers
5
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 context-free language, then there is a number $k$ where, if $s$ is any string in $A$ of length at least $k,$ then $s$ may be ... conditions$:$ for each $i\geq 0,uv^{i}xy^{i}z\in A,$ $v\neq\epsilon$ and $y\neq\epsilon,$and $\mid vxy\mid\leq k.$
0 votes
1 answer
6
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.)}$
0 votes
1 answer
7
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 \#$ $U\rightarrow 0U00\mid \#$ Consider the language $B = L(G),$ ... $p$ for $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$
0 votes
1 answer
8
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}$ $w,t\in\{a,b\}^{*}\}$ $\{t_{1}\#t_{2}\#...\#t_{k}\mid k\geq 2,$ $\text{each}$ $t_{i}\in\{a,b\}^{*},$ $\text{and}$ $t_{i}=t_{j}$ $\text{ for some}$ $i\neq j\}$
0 votes
1 answer
9
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 length for $A$ is the smallest $p$ that is a ... $(01)^{*}$ $\epsilon$ $1^{*}01^{*}01^{*}$ $10(11^{*}0)^{*}0$ $1011$ $\sum^{*}$
0 votes
1 answer
10
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$ ... that $F$ satisfies the three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.
0 votes
0 answers
11
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. Let $p$ be the pumping length for $0^{*}1^{*}$ ... $0^{*}1^{*},$but example $1.73$ shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.
1 vote
1 answer
12
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}=\{www|w\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.)}$0 votes 1 answer 13 How by Pumping Lemma we can prove that “context free grammar generate an infinite number of strings” and here what could be pumping length ? 0 votes 0 answers 14 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}\}$. 0 votes 0 answers 15 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}\}$. 0 votes 0 answers 16 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}\}$. 0 votes 0 answers 17 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)\}$. 0 votes 0 answers 18 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)\}$. 0 votes 0 answers 19 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)\}$. 0 votes 0 answers 20 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\}$. 0 votes 0 answers 21 Show that the following languages on$\Sigma = \{a,b,c\}$are not context-free.$L=\{a^nb^jc^k : k>n,k>j\}$. 0 votes 0 answers 22 Show that the following languages on$\Sigma = \{a,b,c\}$are not context-free.$L = \{a^nb^jc^k:k=jn\}$. 0 votes 0 answers 23 Show that the following languages on$\Sigma = \{a,b,c\}$are not context-free.$L = \{a^nb^j: n\geq(j-1)^3\}$. 1 vote 0 answers 24 Show that the following languages on$\Sigma = \{a,b,c\}$are not context-free.$L = \{a^nb^j : n\leq j^2\}$. 0 votes 0 answers 25 Show that the language$L = \Big\{ a^{n^2} :n\geq 0\Big\}$is not context free. 0 votes 0 answers 26 Is the language$L = \{a^nb^m:n=2^m\}$context free$?$0 votes 0 answers 27 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. 0 votes 0 answers 28 Show that$L=\{ww^Rw:w\in\{a,b\}^*\}$is not a context-free language. 0 votes 0 answers 29 Show that the language$L = \{a^n : n \text{ is a prime number}\}$is not context-free. 0 votes 0 answers 30 Show that the language$L = \{w\in \{a,b,c\}^*: n_a(w) = n_b(w) \leq n_c(w)\}\$ is not context-free.