New answers tagged pumping-lemma
0
Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$.
Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's ...
1
This can also be proved easily using Myhill-Nerode theorem.
Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a
regular language.
(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)
For the ...
2
I don't see how the hint could be useful in applying the pumping lemma except from the fact that there are infinitely many prime numbers. So you start by a picking a word $w$ of the form $a^r$, where $r$ is a prime that is greater than the pumping constant. Then, think how many times you need to pump in order to get a word of the form $a^k$, where $k$ is non-...
2
You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.
0
It seems that you are trying to force the string length to be $p$, which is not necessary. What is required is that $|xy| \leq p$. The length of $w$ can be greater than $p$. Also, $n$ or $m$ can be $p$ or some multiple of $p$, whatever makes the reasoning for the impossibilty of partition of $w$ to satisfy the lemma. With that, I think you can follow ...
0
The language $L$ is not regular. One might think $L$ is regular as it is tempting to think that the number of 010s and the number of 101s in a word are dependent. Yet, as explained by @gnasher729, this is not the case because occurrences of 010 and 101 can be far from each other. It is a bit challenging to prove non-regularity of $L$ using the pumping lemma ...
0
I think it might be useful to understand where the pumping lemma comes from and how it can be proven.
If a language $L$ is regular, there exists a DFA that recognizes it$^1%$.
Let $p$ be the number of states in the DFA.
As a word passes through it, the automaton goes through a sequence of states, as each symbol is consumed.
For a word $w$, if $|w| \ge p$, ...
3
You said:
If I understand correctly, $x$ and $z$ are basically anything on the 2
sides of the string $y^p$ that we're pumping and thus can be anything
in 𝐿.
This is not true. The pumping lemma suggests that for every long enough word $w$ such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma ...
0
The condition $|xy|\leq p$ requires that the selected substring $y$ to be pumped is not too far from the start of the string.
Consider the language $L = \{x |x \in \{0,1\}^* x\ has\ equal\ number\ of\ 0's\ and\ 1's \}$ which can be shown to be a non-regular language via the pumping lemma. To show that this is not regular the usual example string used is $0^...
2
I agree that the way the lemma is written is confusing, a more friendly way to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more human readable now):
The Pumping Lemma: for every regular language $L\subseteq \Sigma^*$, there is a positive pumping constant $p$ such that for ...
1
Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, but its not a good choice for proving non-regularity. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = ...
Top 50 recent answers are included
