COMP4200 Homework 2 Solution

2.

- 𝐴 & 𝐵 are both regular languages, so according to the theorem that regular languages are closed under complement proves that 𝐴̅ & 𝐵̅ are also regular languages.
- Under the theorem that regular languages are closed under intersection and union, we know that equations like 𝐴 ∩ 𝐵 = ̅𝐴̅̅̅∪̅̅̅𝐵̅̅ are regular.
- 𝐴 − 𝐵 can be written as 𝐴 ∩ 𝐵̅
- As said earlier, under the theorem that regular languages are closed under complement 𝐴 & 𝐵̅ are regular.
- Finally since 𝐴 ∩ 𝐵̅ is a regular language, 𝐴 − 𝐵 is also a regular language.