New answers tagged pumping-lemma
1
The minimum pumping length $\ell$ of $(01)^*$ is $2$.
First of all notice that there are no words of length $1$ in the language.
Then, if you look at a formal definition of the pumping lemma for regular languages (what you wrote is still informal) you'll find that the length $|xy|$ of the prefix $xy$ of a word in the language that can be pumped must be $\le \...
1
The pumping lemma of context-free languages means finding $x,y,z,v,u$ such $w=xvyuz, |vu|>0,|vxu|\le p$, and for all $n\in\mathbb N$, $xv^nyu^nz$
The regular pumping lemma means finding only $v,y,u$ where $w=abc,|b|>0,|ab|\le p$ and $ab^nc\in L$. ("a","b","c" here are representing sub-words of w)
So, simply take $x=a,v=b,y=...
1
Let $k=2009$ and $L = \{w : |u_a| \ge k\cdot |u_b|$}. I think it is easier to prove using Myhill-Neorde's Theorem.
Consider the strings $a^k, a^{2k}, a^{3k} \ldots$, we claim that all of these have a $L$-distinguishable suffix. Consider $a^{lk}$ and $a^{mk}$ with $l < m$. Let $x = b^m$. We have $a^{lk}b^m \notin L$ but $a^{mk}b^m \in L$ (Why?). Therefore,...
0
Take pumping length = 4. All strings in the language with length greater than the pumping length must meet some condition. Since there are no strings in the language with length > 4, all these strings, all zero of them, meet any condition, and therefore the language is regular.
That’s true for any finite language where you can just take the pumping ...
1
Every finite language is regular. If $L$ is a finite language and $p$ is larger than the length of all words in $L$, then $L$ satisfies the pumping lemma with the constant $p$. Indeed, every word in $L$ of length at least $p$ can be pumped (vacuously).
0
If $L$ were context-free then so would $L' = d(L \cap (0+1)^*\#(0+1)^*)$ be, where $d$ is the homomorphism that deletes $\#$. However, $L'$ is the language of squares (words of the form $w^2$), which is well-known not to be context-free.
If for some reason you have to prove that $L$ is not context-free directly using the pumping lemma, this suggests looking ...
1
Yes, what you have observed is correct. We can, in fact, always take $N=0$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once.
A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$ such that $ x=uvw$, $|v|\ge 1$ and $\forall z\in \Sigma^*$,
$$uvwz\in L \iff uwz\...
0
A unary language $L$ is context-free iff it is regular iff it is eventually periodic, that is, if the set $N = \{n \in \mathbb{N} : a^n \in L\}$ satisfies the following property: there exist $m \geq 0$ and $r \geq 1$ such that for all $n \geq m$ we have $n \in N$ iff $n + r \in N$.
In particular, any unary language which has zero limiting density (i.e., $\...
3
For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.
Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.
Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)...
0
Delete all numbers from your language $L$, and replace $,$ with $a$ and $;$ as $b$. Then intersect it with the regular language $a^*ba^*ba^*$. You obtain a new language $L' = \{a^n b a^n b a^n : n \in \mathbb{N}\}$. If $L$ is context-free, then $L'$ will be context-free too, as it has been obtained by applying a homomorphism and then intersecting with a ...
0
To convert this question into an easier question to answer, practically, we consider the language $\hat L=\{(a^nb)^n|n\in\mathbb N\}$. Proving this is not context free is enough, since we can give a hommomorphism from $L$ to it by $h(",")=a,\space h(";")=b,\space h(x)=\epsilon$ for every other $x$, and then we get $h(L)=\hat L$.
Now, I think it should be ...
Top 50 recent answers are included
