search
Log In

Recent questions tagged pumping-lemma

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)$}.
asked Jun 25, 2019 in Theory of Computation Naveen Kumar 3 162 views
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.$
asked May 4, 2019 in Theory of Computation Lakshman Patel RJIT 107 views
0 votes
1 answer
6
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$.$
asked May 4, 2019 in Theory of Computation Lakshman Patel RJIT 152 views
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\}$
asked May 4, 2019 in Theory of Computation Lakshman Patel RJIT 102 views
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^{*}$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 168 views
0 votes
1 answer
10
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.
asked Apr 22, 2019 in Theory of Computation Lakshman Patel RJIT 117 views
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.)}$
asked Apr 22, 2019 in Theory of Computation Lakshman Patel RJIT 145 views
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 ?
asked Apr 19, 2019 in Theory of Computation srestha 140 views
...