An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

ANSWERS: SOLUTIONS AND HINTS FOR SELECTED EXERCISES

Chapter 1

Section 1.1

1. 5. Suppose x ∈ S − T. Then x ∈ S and x ∉ T, which means x ∈ S and x ∈ T, that is $x\in S\cap \overline{T}$. So $S-T\subseteq S\cap \overline{T}$. Conversely, if $x\in S\cap \overline{T}$, then x ∈ S and x ∉ T, which means x ∈ S − T, that is $S\cap \overline{T}\subseteq S-T$. Therefore $S-T=S\cap \overline{T}$.
2. 6. For Equation (1.2), suppose $x\in \overline{S_1\cup S_2}$. Then x ∉ S₁ ∪ S₂, which means that x cannot be in S₁ or in S₂, that is x ∈ S₁ ∩ S₂. So $\overline{S_1\cup S_2}\subseteq \overline{S_1}\cap \overline{S_2}$. Conversely, if $x\in \overline{S_1}\cap \overline{S_2}$, then x is not in S₁ and x is not in S₂, that is, $x\in \overline{S_1}\cup \overline{S_2}$. So $\overline{S_1}\cap \overline{S_2}\subseteq \overline{S_1\cup S_2}$. Therefore $\overline{S_1\cup S_2}=\overline{S_1}\cap \overline{S_2}$.
3. 12.
   1. (a) reflexivity: Since |S₁| = |S₁|, so reflexivity holds.