Explore BrainMass

What is the Collection of Decidable Languages Closed Under?

This content was COPIED 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 March 21, 2019, 2:04 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, ...