• edited by
345 views
0 0 votes

Let $L_{1},L_{2},\cdot\cdot\cdot,L_{k}$ be a collection of languages over alphbet $\Sigma$ such that:

  1. For all $i\neq j$, $L_{i}\cap L_{j}=\phi$; i.e., no string is in two of the languages.
  2. $L_{1}\cup L_{2}\cup\cdot\cdot\cdot\cup L_{k} = \Sigma^{\ast}$;i.e., every string is in one of the languages.
  3. Each of the languages $L_{i}$, for $i=1,2,\cdot\cdot\cdot,k$ is recursively enumerable.

Prove that each of the languages is therefore recursive.

Please log in or register to answer this question.

Position:
Show:

Related questions

0 0 votes
1 1 answer
889
889 views
admin asked Jul 21, 2019
889 views
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10...
0 0 votes
0 0 answers
339
339 views
admin asked Jul 21, 2019
339 views
We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the ...
0 0 votes
0 0 answers
267
267 views
admin asked Jul 21, 2019
267 views
Let $L$ be recursively enumerable and let $\overline{L}$ be non-RE. Consider the language$L' = \left\{0w\mid w\ \text{is in}\ L \right\}$Can you say for certain whether $...
0 0 votes
0 0 answers
388
388 views
admin asked Jul 21, 2019
388 views
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.The set of all $TM$ codes for $TM's$ that halt on every input.The set of all $TM$ codes ...