Share
Explore BrainMass

What is the Collection of Decidable Languages Closed Under?

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

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, ...

$2.19