New answers tagged pumping-lemma
1
vote
Is the set of languages satisfying the pumping lemma closed under concatenation?
Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and ...
- 269k
0
votes
Which z should I pick?
We want to show that the language $L_2 = \{0^n: n=2^k, k \ge 0\}$ is nonregular. By way of contradiction, suppose $L_2$ is regular. Let $p$ be the pumping length. Let $z = 0^{2^p}$. Then, $z \in ...
- 1,005
0
votes
Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular
We want to show the language $L = \{0^{2^n}: n \ge 0\}$ is nonregular.
By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$, called the pumping length, such that all ...
- 1,005
1
vote
Prove that the language of regular expressions is not regular
Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character ...
- 4,611
0
votes
What exactly is pumping length in pumping lemma?
A regular language has a finite state machine, and therefore it has a finite state machine with a minimum number of states n. If we examine the first n letters of an input string, there are n+1 states ...
- 24.9k
1
vote
Accepted
How to prove ww^r is context free using pumping lemma for context free languages
The pumping lemma for context-free languages is used to prove that a given language is not a context-free language. There exists a PDA accepting the language $L = \{w w^r: w \in \{0,1\}\}$, and so $L$...
- 1,005
0
votes
Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
The language $L_1 = \{a^n b^m: n, m \ge 0, m \ge n\}$ is not regular. This can be proved using the pumping lemma.
By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$ ...
- 1,005
3
votes
Is this language a context-free language or not?
I do not think the linked question is relevant.
Consider the context-free language $L = \{a^n b^n c^m d^m \mid m,n\ge 0\}$.
Let us consider an example string, $uv = a^3 b^3 c^8 d^8 $.
Assuming $u$ and ...
- 27.2k
8
votes
Accepted
Is this language a context-free language or not?
No, $L_1$ is not necessarily context-free.
For example, let $L=\{0^n1^{3n}\mid n\ge0\}$.
If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$.
So, $L_1=\{1^...
- 33k
1
vote
What exactly is pumping length in pumping lemma?
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.
Your finite automata can ...
- 785
2
votes
Accepted
What exactly is pumping length in pumping lemma?
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by ...
- 1,005
1
vote
What exactly is pumping length in pumping lemma?
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the ...
- 1,257
1
vote
Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q.
After processing $a^p$ you are in a state S that ...
- 24.9k
2
votes
Accepted
Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k < ...
- 22.7k
2
votes
How does Sipser's proof that $0^n1^n$ is not regular work?
If $x$ consists of $p-2$ zeros, $y$ is 0 and $z$ consists of $p$ ones, then $xyz$ is $0^{p-1}1^p$, not $0^p 1^p$. Hence, the particular partition you give is impossible. If $|xy| < p$, then $z$ ...
- 1,005
1
vote
How does Sipser's proof that $0^n1^n$ is not regular work?
With the way you split your string, $|z|$ is $p +1$ and not $p$. Then, $z$ will be $01^p$ and not $1^p$. And with this, the proof stated by Sipser still holds.
- 1,257
0
votes
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
Yes, you can choose different strings of length at least $p$ (where $p$ is the constant given in the pumping lemma) than the one given in the resource; however, not all strings will help you complete ...
- 1,005
0
votes
Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular
In your proof, you assume $p=3$. This would only prove that there does not exist a machine [a finite automata] with three states accepting the given language $A = \{0^n 1^n: n \ge 0\}$. To show the ...
- 1,005
3
votes
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
I have the proof, so please don't bother doing the proof, I just want to know if we can choose different values like I said? I know we can't, but I don't know the reasoning behind it.
Yes, we can.
...
- 966
3
votes
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
The negation of "pumpable" as described in the pumping lemma states:
for all n
exists w in L with |w| > n
for all...
exists...
for which...
You can ...
- 149
Top 50 recent answers are included