7
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ... 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. $\endgroup$ – Hendrik Jan Oct 6 '16 at 8:15
10
$\begingroup$

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^*$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Shubham Singh rawat Oct 5 '16 at 8:52
  • $\begingroup$ @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. $\endgroup$ – Bakuriu Oct 5 '16 at 9:23
  • $\begingroup$ 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... $\endgroup$ – Bakuriu Oct 5 '16 at 9:28
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.