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?

$\endgroup$
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.
$\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$ Apr 26 at 21:17
  • $\begingroup$ Try to enumerate on all prefixes $\endgroup$
    – nir shahar
    Apr 26 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 at 22:03

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.