Question

Show that if \(A\) and \(B\) are regular sets, then so is \(A \cap B\).

Short answer

According to the result of the previous exercise and the definition of a regular set/expression it is proved " \(A \cap B\) is a regular set".

Step-by-step solution

Definition

An expression is a regular expression over some input alphabet I when:

\(\lambda \)is a regular expression

x is a regular expression for all \(x \in I\)

AB is a regular expression whenever A and B are regular expressions.

\(A \cap B\)is a regular expression whenever A and B are regular expressions.

\({A^*}\)is a regular expression whenever A is a regular expression.

By using regular expressions

To proof: If A and B are regular sets, then \(A \cap B\) is also a regular set

PROOF

Let A and B be regular sets.

The complement of a regular set is also a regular set, according to the previous exercise. Thus \(\bar A\) and \(\bar B\) are also regular sets.

Since \(\bar A\) and \(\bar B\) are regular sets, \(\bar A\) can be expressed by some regular expression C and \(\bar B\) can be expressed by some regular expression D.

By the definition of a regular expression, \(D \cup D\) is then a regular expression of the set \(\bar A \cup \bar B\), which implies that \(\bar A \cup \bar B\) is a regular set.

Hence, the complement of the regular set \(\bar A \cup \bar B\) is then also a regular set and thus \(\overline {\bar A \cup \bar B} = A \cap B\) is a regular set.