2
$\begingroup$

Union of two REL is closed under union. I don't understand how is it closed. I followed this link. The have stated:

Here the trick is to simulate both M1 and M2 “simultaneously”. In other words, we design a machine that executes one step of M1, followed by one step of M2, then again one step of M1 and so on.

My question is if the word doesn't belong to either of the machines then how did they decide that the output will be closed? Both the machines can be in an infinite loop and we cannot decide if the word belongs to the language accepted by M1 of M2.

What am I missing here? Also, is there any relation between halting and closure properties of turning recognizable languages?

$\endgroup$

1 Answer 1

3
$\begingroup$

"Closed under union" means that if $L_1,L_2\in RE$, then $L_1\cup L_2\in RE$.

The machine you described will indeed accept a word $w$ if $w\in L_1\cup L_2$. If $w\notin L_1\cup L_2$, then machine might not halt. But that is fine, since we only want to show that the language is in $RE$, not $R$.

$\endgroup$
2
  • $\begingroup$ If I understood this correctly, RE is the superset of languages to which L1 and L2 belong. What is R? $\endgroup$
    – darkexodus
    Aug 10, 2021 at 5:37
  • $\begingroup$ I got it. They are Recursive and Recursively Enumerable. I got confused because we use REC for recursive and REL for recursively enumereable. $\endgroup$
    – darkexodus
    Aug 10, 2021 at 5:47

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .