Tag Info

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