$Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists \:x\in \:A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$

Question

$A\:is\:some\:language\:over\:\sum.\\Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists x\in A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$

I thought to show a non-deterministic Turing machine $T$ that decides $B_A$. I would like to know what do you think about my solution please.

$T=$

"given an input w:

1.if $w=\epsilon$ then: if $\epsilon \in A$ then acceps, otherwise reject.

2.non-deterministically choose a word $x\in A$.

3.if $|x|\leq |w|$ then accept, otherwise reject"

I solved it determinstically and I'm trying to understand the non-determenistic model and I will be glad to know what you think and if this solution is ok.

Thanks.

Answer 1

If we talking about finit $\Sigma$, and decidable A, then a simple solution to the problem is the following turing machine: For a given word $w\in {\Sigma}^*$, with $|w|=n \in \mathbb{N}$,

check for every word $w' \in {\Sigma}^*$ with $|w'|\le n$ if $w'\in A$. if we find one, accept, otherwise reject.