CODEWITHSUNDEEP
algorithmproductdifferenceturing-machinesset-theory
James the Great
James the Great

Reputation: 951

Closure Properties of recursively enumerable languages

Please consider the following question:

Let L1 and L2 be two languages. Prove or disprove the closedness of the class of r.e. languages under

  1. difference (L1 - L2)

  2. product (L1 x L2) (Try to prove product under the assumption that is known where the word of L1 ends as wells as for the case where it is not known.

Here, closedness means that if L1 and L2 can be accepted by a touring machine, then also (L1 - L2) or (L1 x L2)

Notes

I am able to figure out a solution for union and complement (union: closed; complement: not closed), but not for the above (difference or product).

Upvotes: 1

Views: 1875

Answers (1)

collapsar
collapsar

Reputation: 17238

1) RE is not closed under difference.

Proof: Assume it was.

Let Sigma be the alphabet of an arbitrary RE language L. Sigma^* is RE (TM just checks that the input string either only contains symbols from Sigma or else is empty). If RE would be closed under difference, in particular Sigma^* - L would be RE. But then any RE language would be recursive ( decidable ). However, there are undecidable RE languages ( cf. halting problem ).

2) RE is closed under Cartesian product

Proof sketch: Assume first that an oracle provide the correct partition of the input string into words from L1, L2. In that case, run TMs T1, T2 to check containment in L1, L2, resp., sequentially on their inputs. This setup terminates iff both TMs terminate.

Next assume that there is no oracle. For any given input string w, there are length(w)+1possible partitions. Run length(w)+1 copies of the concatenated TMs T1, T2 in parallel, one for each partition, on the inputs from the respective partition. This setup terminates iff at least one of the cloned TM concatenation terminates which is equivalent to the input string portions are members of L1, L2, resp.

Upvotes: 1

Related Questions