# Proving the regularity of a certain language

I've been fumbling around with this problem for the last hour, and I'm incredibly stumped.

Let $A = \{\; 0^ku0^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$. Show that $A$ is regular.

The language obviously satisfies the Pumping Lemma, but that is not conclusive for regularity. How on earth do I prove that this language is regular? I'm aware of all the normal methods (closed-under, etc), but I cannot for the life of me figure out the appropriate condition to continue.

It is a trick question. You can find a simpler form to describe the language.

• ... and yes, I know the solution, but thought it would be more helpful to give a nudge in the right direction instead of writing it down in full. Just my idea. Oct 6, 2016 at 8:15

The language can be re-written as $A=\{0u0 \mid u\in \Sigma^*\}$.

The basic idea is that no matter what the value of $k$ is, it all gets "absorbed" into $u$ which is the complete language $\Sigma^*$.

• but since 'u' is the complete language couldn't it be the empty string as well? what will be the implications if 'u' is the empty string? Oct 5, 2016 at 8:52
• @ShubhamSinghrawat Yes, but that has no implication. Remember a language is regular if there exist a DFA that recognizes it. consider the word $w=0^3 \epsilon 0^3 \in A$. This answer is telling you that you instead of seeing it in that way you can see it as the word $w = 0^1 u 0^1$ with $u = 0^20^2 \in \Sigma^*$ and you can see that this matches the definition of the words in $A$, but also the definition of this answer. In the end the DFA for A is simply: check that the first letter is $0$ and that the last letter is $0$, everything else doesn't matter. Oct 5, 2016 at 9:23
• If that wasn't clear enough,an NFA that recognizes $A$ is just $N = (Q, \Sigma, \Delta, q_0, \{q_2\})$ with $Q = \{q_0, q_1, q_2\}$ and $$\Delta = \{(q_0, 0, q_1), (q_1, 0, q_2), (q_2, 0, q_2)\} \cup \{(q_1, x, q_1) \mid x \in \Sigma \setminus \{0\}\} \cup \{(q_2, x, q_1) \mid x \in \Sigma \setminus \{0\}\}$$ and in fact this is almost a DFA except that it's not total... Oct 5, 2016 at 9:28

If it were this language:

$B = \{\; 0^k1u10^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$

you'd be in trouble. $B$ is not regular.

The key problem is that when trying to recognise strings from $B$, you need to "remember" an unbounded amount of information from the initial string of $0$s (how many there were), because you need to distinguish between the strings like $0^k1...10^k$ and the ones like $0^k1...10^j$ (where $j≠k$). Regular expressions (or DFAs) are unable to express this sort of "unbounded memory".

$A$ looks like it has the same problem, but actually there's no need to tell the "balanced" and "unbalanced" cases apart. For any string $0^ku0^j$ (whether or not $j$ and $k$ are equal, but both are at least 1), you can also write it as $0v0$, where $v=0^{k-1}u0^{j-1}$. Such a string also meets the rule for $A$'s strings (by choosing $k=1$ and $u=v$), and so it didn't actually matter that the leading and trailing $0$s were balanced after all.