Intereting Posts

Difference between a “theory” in logic and a “system of axioms”
Questions of an exercise in Lebesgue integral
How did Hermite calculate $e^{\pi\sqrt{163}}$ in 1859?
Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?
Finding coefficient of generating function
Geodesics of a “diagonal” metric
Differentiate vector norm by matrix
Cohomology of projective plane
Proof of orthogonal matrix property: $A^{-1} = A^t$
Distribution of points on a rectangle
Integral: $\int^\infty_{-\infty}\frac{\ln(t+1)}{t^2+1}\mathrm{d}t$
proof of l'Hôpital's rule
Suppose that $p$ ≥ $q$ ≥ $5$ are both prime numbers. Prove that 24 divides ($p^2 − q^2$)
Maximization with xor operator
Does $y(y+1) \leq (x+1)^2$ imply $y(y-1) \leq x^2$?

Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a palindrome.

Now I split $y$ into $uvw$, where $v \ne \epsilon$ contains a state visited more than once. If the language is regular then $xuv^iwz$ is within the language $\forall i \ge 0$.

I choose $i = 2$, then $uv^2w = (abb)^n$ where $n > k$.

- Is computer science a branch of mathematics?
- Lower bound for finding second largest element
- Degeneracy in Linear Programming
- How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?
- Distance between a point and a m-dimensional space in n-dimensional space ($m<n$)
- How to find a function that is the upper bound of this sum?

Then $xuv^2wz = (abb)^n(bba)^k$ where $n > k$, which is not a palindrome.

Firstly, is my reasoning for this particular proof correct? I’m unsure about how to properly apply the pumping lemma to this problem. And secondly the question asks me to state a proof for palindromes *in general*, whereas I only attempted to prove it for a single case. Is there an example I can choose which proves the conjecture for all palindromes? I assume not, seeing as I can’t think of how that could be represented using regular expressions.

- In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
- Number of bit strings of length $n$ with no $k_1+1$ consecutive 0s and no $k_2+1$ consecutive 1s.
- Show $\{0^m1^n | m \neq n\}$ is not regular
- Undecidable language problems.
- Why can't we use memoization to parse unambiguous context-free grammars in linear time?
- Distance between a point and a m-dimensional space in n-dimensional space ($m<n$)
- Computability, Continuity and Constructivism
- Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$
- Why is it hard to parse unambiguous context-free grammar in linear time?
- Computing the $n^{\textrm{th}}$ permutation of bits.

Your proof is incorrect, for instance you only handle a subset of palindromes (and regular languages can have non-regular subsets). I’m not quite sure what you’re trying to do there, but for reference here’s my version of the proof using the pumping lemma. I hope it opens up valuable insights.

(using $s^R$ to denote the reverse of $s$)

Let $L = \{s : s = s^R\}$ or the set of all palindromes (strings that are equal to their reverse strings).

If $L$ is regular, there must be a pumping length $p \ge 1$ so that for each $s \in L$, if $|s| \ge p$ we can write $s$ as $xyz$ so these three conditions apply:

- $y \neq \epsilon$ ($y$ has at least one character/symbol, in other words $|y| \ge 1$)
- $|xy| \le p$
- for all $i \in \mathbb{N} \cup \{0\}$, $xy^iz \in L$

Let $s = a^pba^p$. We can see $s$ is a palindrome, so $s \in L$. Also, $|s| = 2p + 1 \ge p$.

Because of the two first conditions, all possible $xyz$ divisions of $s$ are in the following form:

- $x = a^k$
- $y = a^m$
- $z = a^{p-m-k}ba^p$

for some non-negative integers $k, m$ so that $k + m \le p$ and $m \ge 1$.

Now let’s demonstrate that $xy^iz \in L$ doesn’t hold for some values of $i$.

For example, let $i = 2$. Then $$xy^2z = xyyz = a^ka^ma^ma^{p-m-k}ba^p$$

which can be simplified further as $$a^ma^pba^p = a^{p+m}ba^p$$

The reverse string, $(xy^2z)^R$ is $a^pba^{p+m}$. Because we know that $m \ge 1$, it follows that $$a^pba^{p+m} \neq a^{p+m}ba^p$$ Therefore, $xy^2z \notin L$ under any possible divisions $xyz$ while following the three conditions ruled by the lemma. Hence, $L$ must be non-regular.

- You can choose
*any*string $s \in L$, as long as $|s| \ge p$. Make life easy for yourself and pick a string that makes the rest of the lemma easy to apply. I picked $a^pba^p$ simply to reduce the complexity of different $xyz$ divisions. - For a language to be non-regular, you must prove there are
*no*possible divisions $xyz$ that are possible according to the three criteria. It’s not enough to demonstrate that*some*$xyz$ division fails at the $xy^iz \in L$ phase.

Your proof is no good; the basic idea is fatally flawed. You are asked to use the pumping lemma to prove that $P$, the set of all palindromes, is irregular. Instead, you picked some subset of $P$, namely the set of strings $$X =\{\epsilon, \mathtt{abbbba}, \mathtt{abbabbbbabba}, \ldots\},$$ and tried to show that other set is irregular. But even if you were to succeed in that, it wouldn’t help you solve the problem, because the question wasn’t about $\epsilon, \mathtt{abbbba}, \mathtt{abbabbbbabba}, \ldots$; it was about the set of all palindromes.

Showing that $X$ is not regular does not help you show that the set of palindromes was irregular; why should it? Well, I guess you want to say “The set of palindromes contains $X$, and $X$ is not regular, so the larger set can’t be regular either.” But this is nonsense. The language $(\mathtt{a}+\mathtt{b})^\star$ contains $X$ also, and it is as regular as can be.

The way you do a proof using the pumping lemma should look like this. You imagine playing a game against an adversary, Mr. Pumping Lemma.

- Mr. Pumping Lemma gives you a constant $p\gt 0$, and claims that all palindromes of length $p$ or greater have a pumpable part near the beginning.
- You pick some single palindrome $x$ whose length is at least $p$. You say “This string $x$ has length $p$ or greater, and does not have a pumpable part near the beginning.”
- Mr. Pumping Lemma says “yes, it does” and divides your string $x$ into $uvw$ so that $|uv|\le p$, $|v|\gt 0$. The $v$ part is the pumpable part, and $|uv|\le p$ means that it is close to the beginning of the string.
- You pick some number $n \ne 1$ and show that $uv^nw$ is not a palindrome. (What $n$ should you pick here?) If you can do this, you say “see, I pumped $v$ as you said, and the result was not a palindrome,” and you win. If not, Mr. Pumping Lemma wins.

You must make a clever move in step 2 so that no matter what Mr. Pumping Lemma does is step 3, you can always win in step 4. If you pick the wrong string in step 2, Mr. Pumping Lemma can confound you. For example, if you were to pick $x = \mathtt{a}^p$ in step 2, that would be a bad move, because then in step 3, Mr. Pumping Lemma could take $u=\mathtt{a}^i, v = \mathtt{a}^{p-i}, w = \epsilon$, and then no matter what $n$ you picked in step 4, the resulting $uv^nw$ would still be a palindrome and you would lose.

Fortunately in this case it’s not hard to make a good choice in step 2. I suggest that you try $x=\mathtt{a}^{p+1}\mathtt{b}\mathtt{a}^{p+1}$ and see how that goes.

Consider the language

$$

L = \left\{ w^p : w \in L \right\}, L \subseteq A^{*}.$$ Where $A$ is the

input alphabet of the automaton that recognizes $L$.

where $w = a_1a_2…a_n, \left| w \right| = n $ and $w_p = a_na_{n-1}…a_1, \left| w_p \right| = n $

From a general approach using Kleene’s theorem we know that a language is regular iff it is rational. However, in order for language $L$ to be regular/recognisable from a finite automaton it must have an infinite set of states, which is impossible. Thus, Kleene’s theorem guarantees that this language is NOT regular.

Things are getting a bit harder when we have to prove our claim using the pumping lemma.

By presuming the language is regular, there exists a number $p$ (length of pump) so that the following conditions are true:

$$ \forall i \geq 0, xy^iz \in L$$

$$ \left| y \right| > 0 $$

$$\left| xy \right| \leq p $$

You should try with the word $w_p$ and go through all 3 conditions of the pumping lemma. The key to the solution is condition Number 3 since the first condition cannot always lead to a contradiction.

- $C^2 $embedded in holder space?
- Evaluating this integral : $ \int \frac {1-7\cos^2x} {\sin^7x \cos^2x} dx $
- How to prove a trigonometric identity
- How to prove that $\lim_{(x,y) \to (0,0)} \frac{x^3y}{x^4+y^2} = 0?$
- Character space of $L^{1} (\mathbb Z)$
- How to prove(or disprove) $\begin{vmatrix} A&B\\ B&A \end{vmatrix}=|A^2-B^2|$
- Express logic puzzles with proposition calculus notation
- Structure of antiautomorphisms of a group
- Summing Finitely Many Terms of Harmonic Series: $\sum_{k=a}^{b} \frac{1}{k}$
- Proposition: $\sqrt{x + \sqrt{x + \sqrt{x + …}}} = \frac{1 + \sqrt{1 + 4x}}{2}$.
- Showing that the space $C$ with the $L_1$ norm is incomplete
- Why is $(3,x^3-x^2+2x-1)$ not principal in $\mathbb{Z}$?
- Difference between $\sum$ and $\int$
- Is there a geometrical definition of a tangent line?
- Construct a Borel set on R such that it intersect every open interval with non-zero non-“full” measure