0
$\begingroup$

On an old worksheet I came across the question

If L1 and L2 are two Turing decidable languages, then show that 𝐿1∪𝐿2 and 𝐿1𝑜𝐿2 are Turing decidable languages (high-level description with stages is enough).

How do I go about answering this without being given a language to work from?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Both $L_1$ and $L_2$ are decidable. Hence, they have algorithms $A_1$ and $A_2$ (respectively) that decide them.

Try to create a new turing machine (algorithm) using the two algorithms $A_1$ and $A_2$.

For example, for the union $L_1\cup L_2$, you can create the following algorithm:

  • run $A_1$ on the input. If it accepted, then also accept.
  • else, run $A_2$ on the input, and return what $A_2$ returned.
Improve this answer
$\endgroup$
3
  • $\begingroup$ I was able to understand this and I was able to do the same if it was intersection, but how does this work for concatenation? Thanks by the way! $\endgroup$
    – ChrisAmwell
    Apr 26, 2021 at 21:17
  • $\begingroup$ Try to enumerate on all prefixes $\endgroup$
    – nir shahar
    Apr 26, 2021 at 21:35
  • $\begingroup$ For each enumeration check if each of the two parts are in $L_1$ and $L_2$ respectively $\endgroup$
    – nir shahar
    Apr 26, 2021 at 22:03

Your Answer

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

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