0 votes 0 votes If for every RE there exist a TM that accepts it, is it possible that for 2 different RE languages there exists a single TM that accepts them? Theory of Computation theory-of-computation self-doubt + – tusharb asked Jul 20, 2022 tusharb 483 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes This problem can be solved using the closure property of REL. The language generated by union of 2 RELs is a new REL. And as the new generated language is REL that means we can build a Turing Machine for it. This new TM will accept both the languages. REL1 ∪ REL2 ≡ REL. tanBit answered Jul 20, 2022 tanBit comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Jul 20, 2022 reply Follow Share Then build a TM for sigma* and it'll accept any language 😉 2 votes 2 votes Shaik Masthan commented Jul 21, 2022 reply Follow Share You may have two different TMs which accept same language. But you can't have one TM which accepts two different languages. Language accepted by TM means, produces Yes for the strings which are in it. And No for other strings. 1 votes 1 votes Please log in or register to add a comment.