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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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, 2016 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^*$.

Improve this answer
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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