CMIMC 2016 Power Problem L.5

Past Contests CMIMC CMIMC - 2016 Power
1

One natural question to ask is how regularity behaves under certain string and set operations. These might include the union and intersection of two languages as well as their concatenation. It turns out that regular languages are closed under many different kinds of operations. The following problems will ask to prove closure of regularity under different types of operations. They are roughly ordered by difficulty, with a few notable exceptions.

(a) COMPLEMENT: Let L be a regular language over the alphabet \Sigma, and set

L^{c}=\left\{x \in \Sigma^{*} \mid x \notin L\right\}

Prove that L^{c} is also regular.

(b) INTERSECTION: Suppose A and B are two regular languages over a common alphabet \Sigma. Prove that

A \cap B=\left\{x \in \Sigma^{*} \mid x \in A \text { and } x \in B\right\}

is also regular.

(c) UNION: Suppose A and B are two regular languages over a common alphabet \Sigma. Prove that

A \cup B=\left\{x \in \Sigma^{*} \mid x \in A \text { or } x \in B\right\}

is also regular.

(d) SET DIFFERENCE: Suppose A and B are two regular languages over a common alphabet \Sigma. Prove that

A \backslash B=\left\{x \in \Sigma^{*} \mid x \in A \text { and } x \notin B\right\}

is also regular. (Hint: use some of the results from above!)