# Tag Info

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 ...

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 ...
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 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 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 ...