patternModerate
Proving the regularity of a certain language
Viewed 0 times
provingregularitythelanguagecertain
Problem
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.
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.
Solution
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^*$.
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^*$.
Context
StackExchange Computer Science Q#64238, answer score: 10
Revisions (0)
No revisions yet.