Intereting Posts

How to prove that this set is closed?
Group $G$ of order $p^2$: $\;G\cong \mathbb Z_{p^2}$ or $G\cong \mathbb Z_p \times \mathbb Z_p$
Easy partial fraction decomposition with complex numbers
Can two integer polynomials touch in an irrational point?
for any $A\subseteq X$, $f(\overline{A})\subseteq\overline{f(A)}$ , if and only if $f: X \to Y$ is continuous.
Combinatorial proof of $\sum_{k=0}^{n} \binom{n+k-1}{k} = \binom{2n}{n}$
Reference for multivariable calculus
$f: \Omega \rightarrow \Omega$ holomorphic, $f(0) = 0$, $f'(0) = 1$ implies $f(z) = z$
Applying Central Limit Theorem to show that $E\left(\frac{|S_n|}{\sqrt{n}}\right) \to \sqrt{\frac{2}{\pi}}\sigma$
Help with a limit of an integral: $\lim_{h\to \infty}h\int_{0}^\infty{{ {e}^{-hx}f(x)} dx}=f(0)$
Is this *really* a categorical approach to *integration*?
List of interesting math podcasts?
Normal subgroup where G has order prime
Prove the following series $\sum\limits_{s=0}^\infty \frac{1}{(sn)!}$
Good problem book in differential geometry

I’m going through Michael Sipser’s Introduction to the Theory of Computation, and in one of the exercises we are asked to show that $\{0^m1^n | m \neq n\}$ is not a regular language (i.e. is not accepted by a finite automaton). The author gives two proofs, one of them by directly using the pumping lemma on the string $0^p1^{p+p!}$, where $p$ is the pumping length.

I came up with a different solution while reading the answer, which is probably incorrect because the textbook proof is more complicated. I was hoping someone could tell me where the error is: take $01^{p+1}$. Then $01^{p+1}=xyz$ for some $|y|>0$, $|xy|\leq p$ and y can be pumped. Then necessarily $y=0$, because $(01^m)$ can’t be pumped for $1 \leq m$. This means $0^{p+1}1^{p+1}$ is in the language, which is a contradiction.

Did I make a mistake, and if so where? Thanks.

- Using exchange argument in proving greedy algorithm
- Properties of quadrilaterals resulting from perspective projection of rectangle of known aspect ratio
- Floating point arithmetic
- A graph problem
- Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$
- Why can't reachability be expressed in first order logic?

- Reduction from Hamiltonian cycle to Hamiltonian path
- Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations
- Try not to get the last piece, but with a twist!
- Shortest paths from $s$ by weight which contain even number of edges
- Concrete FFT polynomial multiplication example
- Recognizable vs Decidable
- Are points on the complex plane sufficient to solve every solvable equation composed of the hyperoperators, their inverses, and complex numbers?
- What is the algorithm hiding beneath the complexity in this paper?
- Where can I learn more about the “else” operation / “else monoid”?
- Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?

It appears that you’ve misunderstood the use of the pumping lemma. You want to show that **no matter how** you decompose $01^{p+1}$ into $xyz$ with $|xy|\le p$ and $|y|>0$, there is an $n\ge 0$ such that $xy^nz\notin L$. You want to do this because the pumping lemma says that if $L$ were regular, you could find at least one decomposition such that $xy^nz\notin L$ for all $n\ge 0$.

Suppose that you decompose $01^{p+1}$ as $x=0$, $y=1^k$ with $1\le k\le p-1$, and $z=1^{p+1-k}$. Then

$$xy^nz=01^{nk}1^{p+1-k}=01^{p+1+(n-1)k}\;.$$

Since $n\ge 0$, $p+1+(n-1)k\ge p+1-k$. Moreover, $k\le p-1$, so $$p+1-k\ge p+1-(p-1)\ge 2\;,$$ and therefore $xy^nz\in L$ for all $n\ge 0$. In other words, there is a possible decomposition of $01^{p+1}$ that cannot always be pumped outside of $L$. Since this is what we would expect if $L$ were regular, this does not prove that $L$ is **not** regular.

- Does square difference prove that 1 = 2?
- Irreducibility is preserved under base extension
- Proving that surjective endomorphisms of Noetherian modules are isomorphisms and a semi-simple and noetherian module is artinian.
- Why is $n_1 \sqrt{2} +n_2 \sqrt{3} + n_3 \sqrt{5} + n_4 \sqrt{7} $ never zero?
- Error in argument regarding the Cayley Hamilton theorem
- Other ways to deduce Cyclicity of the Units of certain groups?
- How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?
- 2 Tricks to prove Every group with an identity and x*x = identity is Abelian – Fraleigh p. 48 4.32
- Galois group of $x^6-2$ over $\Bbb Q$
- Looking for a problem where one could use a cardinality argument to find a solution.
- Proving :$\arctan(1)+\arctan(2)+ \arctan(3)=\pi$
- The Cantor set is homeomorphic to infinite product of $\{0,1\}$ with itself – cylinder basis – and it topology
- multiplicative Euler's $\phi$ function
- camel hump with trigonometry
- Is there a fundamental theorem of calculus for improper integrals?