# Tag Info

• 5,925
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

### prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

There is a unique path in the derivation tree that leads from the axiom $S$ to the terminal symbol $\#$. An idea would be to turn this tree upside down along that path. This solution follows the ...
• 27.2k
1 vote

### If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

If $L$ is a language of $A^*$ and $u, v$ are words, let $$u^{-1}Lv^{-1} = \{ x \in A^* \mid uxv \in L \}$$ It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is ...
• 5,925
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
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
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
Accepted

### Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode

Let $P$ be the set of all primes. Show that the words $\{b^p : p \in P\}$ belong to different equivalence classes.
• 269k
1 vote

### Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's

Here is how to construct a regular expression for the set of strings over $\{a,b\}$ which contain an even number of $a$'s and at most one $b$. Strings that contain no $b$ are of the form $a^n$, where \$...
• 269k

Only top scored, non community-wiki answers of a minimum length are eligible