Chapter 12.2, Problem 54ES

a. Let A be a finite-state automaton with input alphabet $\sum$ , and suppose $L\left(A\right)$ is the language accepted by A. The complement of $L\left(A\right)$is the set of all strings over $\sum$ that are not in $L\left(A\right)$. Show that the complement of a regular language is regular by proving the following: $L\left(A\right)$is the language accepted by a finite-state automaton A, then there is a finite-state automaton $A^{\prime }$that accepts the complement of $L\left(A\right)$.

b. Show that the intersection of any two regular languages is regular as follows: First prove that if $L\left(A_1\right)$and $L\left(A_2\right)$are languages accepted by automata $A_1$ and $A_2$, respectively, then there is an automaton A that accepts ${\left(L\left(A_1\right)\right)}^c\cup {\left(A\left(A_2\right)\right)}^c$. Then use one of Dc Morgan’s laws for sets, the double complement law for sets, and the result of part (a) to prove that there is an automaton that accepts $L\left(A_1\right)\cap L\left(A_2\right)$ .