1
$\begingroup$

I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a language A = { a2n: n >= 0 }, all strings of a's which length is a power of 2. So here's where I get confused, if I have A*, then I can have (aa)*, which could then lead to (aa)(aa)(aa) = aaaaaa, and this has a length that is not a power of 2. What part of my logic here is wrong?

$\endgroup$
0
$\begingroup$

You're confusing the definition of $A^{\ast}$ and $A$. It is only $A$ in your example that contains strings of $a$s whose lengths are powers of two. $A^{\ast}$ does not have this restriction - it has that restriction that its strings are made up of strings from $A$.

So the individual components of each string in $A^{\ast}$ have to have lengths of powers of two (because they're from $A$), but together we only get that for every string $a^{m}$ in $A^{\ast}$ there is some set $N = \{n_{1},\ldots,n_{k}\}$ (different for each string) such that $m = \sum_{n_{i} \in N} 2^{n_{i}}$.

$\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.