Problem Set 10

Regular Languages

1 Closure

1.1

Let $A$, $B$ be regular languages. Show that $A \cap B$ is also regular.

Solution

By De Morgan’s Law, we know that $\overline{A \cap B} = \overline{A} \cup \overline{B}$. Thus, $A \cap B = \overline{\overline{A} \cup \overline{B}}$.

Since $A$ and $B$ are regular, and regular languages are closed under union and complement, we have $\overline{A}$, and $\overline{B}$ are regular. This implies $\overline{A} \cup \overline{B}$ is regular. This implies $\overline{\overline{A} \cup \overline{B}} = A \cap B$ is regular as required.

Alternatively, use the same construction as the one from the lecture for $A \cup B$, the only difference is a state $(x, y)$ should be accepting if and only if $x$ is accepting in the DFA for $A$ and $y$ is accepting in the DFA for $B$.

1.2

Let $A$, $B$ be regular languages. Show that $A \Delta B$ is also regular, where $A \Delta B$ is the symmetric difference of $A$ and $B$.

Solution

Let $A, B$ be regular languages. Since we’ve shown that regular languages are closed under complementation, union and intersection, $(\overline{A} \cap B) \cup (\overline{B} \cap A) = A\Delta B$ is regular.

Alternatively, use the same construction from the lecture for $A \cup B$. The only difference is a state $(x, y)$ should be accepting if and only if $x$ is accepting in the DFA for $A$ if and only if $y$ is not accepting in the DFA for $B$.

1.3

Let $w$ be any string. Let $w^R$ be the reversal of a string. I.e. if $w = w_1w_2...w_n$, $w^R = w_nw_{n-1}...w_1$. Let $A$ be any language. Then $A^R = \{w^R: w \in A\}$ is the reversal of the language.

Show that if $A$ is regular, then so is $A^R$.

If you construct a NFA, you do not need to justify why it is correct.

Hint: It might be helpful to think of how you would do it for a DFA with a single accept state.

Solution

Let $A$ be a regular language with DFA $M$. We’ll construct an NFA $N$ for $A^R$.

If $w \in M$, then $\delta(q_0, w) = p$ for some accepting state $p$. Thus, reading the string in reverse with transitions reversed starting at $p$ should lead you back to $q_0$. The only problem is that there might be multiple accept states! To address this, create a new start state and “guess” which was the correct accept state by having an $\epsilon$ transition to each accept state in $M$!

Slightly more formally, $N$ is $M$ with all the transitions reversed. $N$ has a new start state that $\epsilon$-transitions to every accept state in $M$. Set the unique accept state in $N$ as the start state in $M$.

2 Finite Languages

2.1

Show by induction that finite languages are regular.

We claim that for all $n \in \mathbb{N}$ if $A \subseteq\Sigma^*$ is such that $|A| = n$, then $A$ is regular. By induction.

Solution

Base case. For the base case, we need to show that the empty set is regular. In particular, consider the DFA consisting of a single rejecting state with a self-loop on all characters. Since there is no accepting state, this DFA rejects every string, and thus the language of this DFA is $\emptyset$.

Inductive step. For the inductive step, let $k \in \mathbb{N}$ be any number and assume all languages of size $k$ are regular. Let $A$ be a language of size $k +1$. Write out $A = \{a_1,...,a_{k+1}\}$. Then we have that $A = \{a_1,...,a_k\} \cup \{a_{k+1}\}$. Then $\{a_1,...,a_k\}$ is a set of size $k$, which is regular by the inductive hypothesis. Furthermore, we showed that singletons sets are regular in class, so $\{a_{k+1}\}$ is also regular. Then since regular languages are closed under union, we have $\{a_1,...,a_k\} \cup \{a_{k+1}\} = A$ is regular as required.

2.2

A language $A$ is cofinite if $\overline{A}$ is finite. Show that if $A$ is cofinite, then $A$ is regular.

Solution

Let $A$ be a cofinite language. Then $\overline{A}$ is finite and thus regular by the previous problem. Since regular languages are closed under complementation, we have $\overline{\overline{A}} = A$ is regular.

3 Regular

Use any method you like to prove that the following languages are regular. The alphabets are given at the start of the problem. Note that if you find a DFA/NFA/regex, you do NOT need to prove that it is correct.

For extra practice, try to find BOTH an automaton and a regex for each language.

Either DFA/NFA/regex is fine! If you’re drawing an automata, make sure to tell me what type of automata you’re drawing.

Eventually, you might prefer automata to regex or vice versa. Both are useful; for some problems, regex is easier, and for others, automata are easier.

I like to try regex first since that is faster, and if I get stuck, I try an NFA.

3.1

$\Sigma = \{0,1\}$

\[A_1 = \{w : w \text{ starts with 0 and has even length or starts with 1 and has odd length}\}\]

Solution

Regex: $(0\Sigma | 1) (\Sigma^2)^*$.

3.2

$\Sigma = \{0,1\}$ \[A_2 = \{w : w \text{ ends with 11}\}\]

Solution

Regex: $\Sigma^*11$.

3.3

$\Sigma = \{0,1\}$ \[A_3 = \{w: w \text{ contains an equal number of occurrences of the substring 01 and 10}\}\]

Solution

Regex: $0(0^*1^+0^+)^* | 1(1^*0^+1^+)^*$

3.4

$\Sigma = \{0\}$ \[\text{Mult}6_u = \{w : \text{number of 0s in $w$ is a multiple of 6} \in \mathbb{N}\}\]

Solution

Regex: $(000000)^* = (0^6)^*$

3.5

$\Sigma = \{0,1\}$. \[\text{Mult}6_b= \{w \in \{0,1\}^*: w \text{ is the binary representation of a multiple of 6}\}\] is regular.

Here are some strings in $\text{Mult}6_b$. \[ \begin{aligned} \texttt{0110} \\ \texttt{1100} \\ \texttt{001100} \\ \epsilon \end{aligned} \]

Solution

Note that $\text{Mult}{6}_b = \text{Mult}{2} \cap \text{Mult}{ 3 }$ where

\[\text{Mult}{2} = \{w : w \text{ is the binary representation of a multiple of 2}\}\]

and

\[\text{Mult}{3} = \{w : w \text{ is the binary representation of a multiple of 3}\}\]

By the closure properties, it suffices to show that $\text{Mult}{3}$ and $\text{Mult}{2}$ are both regular.

$\text{Mult}_2$ is simply “ends with 0 or is the empty string”, which has regex $\Sigma^*0 | \epsilon$, and we saw $\text{Mult}_3$ in the last problem set.

3.6

$\Sigma = \{y,d\}$. $y$ represents a step from you, and $d$ represents a step from your dog. A string in $\Sigma^*$ represents a sequence of steps from you and your dog. Let $\mathrm{DogWalk}$ be the set of strings representing walks where you and your dog end up at the same spot, and your dog is always at most two steps ahead or two steps behind you.

Here are some strings in $\mathrm{DogWalk}$:

\[ \begin{aligned} yydd \\ ydddyy \\ ydyd \\ \epsilon \end{aligned} \] Here are some strings not in $\mathrm{DogWalk}$ \[ \begin{aligned} & yyd & (\text{You don't end up in the same place!}) \\ & yddddyyy & (\text{Your dog is too far ahead after the 5th character!}) \\ & yydyyddd & (\text{You are too far ahead after the 5th character}) \end{aligned} \]

Show $\mathrm{DogWalk}$ is regular.

Solution

Regex: $(y(yd)^*d | d(dy)^*y)^*$