Explore BrainMass

What is the Collection of Decidable Languages Closed Under?

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Show that the collection of decidable languages is closed under the operations of
a. union.
b. concatenation.
c. star.
d. complementation.
e. intersection

© BrainMass Inc. brainmass.com October 24, 2018, 8:58 pm ad1c9bdddf

Solution Preview

a) Union
Proof: If L1 and L2 are recognizable by M1 and M2 (respectively), then L1UL2 is recognized by a machine that simulates M1 and M2 in parallel, accepting if either M1 or M2 accepts

b) Concatenation
Proof: If L1 and L2 are recognized by M1 and M2 (respectively), then construct M3: On input w, ...