\documentclass{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{enumitem}
\begin{document}

\section*{Kyan L.C. Automata Theory Midterm - Problem 1}

Let $\Sigma = \{0, 1\}$ and let $D = \{w \mid w$ contains an equal number of occurrences of the substrings $01$ and $10\}$. Thus $101 \in D$ because it contains a single $01$ and a single $10$ but $1010 \notin D$ because it contains a single $01$ but two $10$s. Show that $D$ is a regular language.

\bigskip

\textbf{Answer:}

Every time the input switches from $0$ to $1$, we have $01$. Every time it switches from $1$ to $0$, we have $10$. So, the number of $01$ and $10$ substrings can differ by at most by $1$. If a string starts with $0$ and ends with $0$ or starts with $1$ and ends with $1$, the counts of $01$ and $10$ substrings are equal. If a string starts with $0$ and ends with $1$ or starts with $1$ and ends with $0$, the counts differ by $1$. $D$ includes only strings where the counts are equal.

So, we can construct a DFA that keeps track of the current symbol ($0$ or $1$) and the parity of the counts of $01$ and $10$ substrings. Our states can be \texttt{even}, \texttt{odd}, \texttt{start0}, and \texttt{start1}. We start in \texttt{even} either way. Then, when reading a symbol that does not change from the previous symbol, stay in the current state. On reading a symbol that changes from the previous symbol, if moving from \texttt{even} then go to \texttt{odd}. If going from \texttt{odd} then go to \texttt{even}. The DFA accepts when we end in \texttt{even}.

Since we can make a DFA to recognize $D$, $D$ is a regular language.

\newpage

\section*{Problem 2}

Let $\Sigma = \{0, 1\}$ and let $B_3 = \{w \mid w$ is a proper binary representation of a number divisible by $3\}$, where ``proper'' means the representation has no leading $0$s unless the entire string is just one zero. Is $B_3$ a regular language?

\bigskip

\textbf{Answer:}

\textbf{Yes}, it is regular.

To start: the strings can’t have leading zeroes. A binary number is divisible by $3$ based on the modulo $3$ remainder of its value. We can construct a DFA that represents the remainders ($0$, $1$, and $2$) when divided by $3$. The accepting state only accepts when the remainder is $0$, or the input is divisible by $3$. Since we can construct a DFA (shown below) for the language, we can conclude that it is regular.

\begin{center}
    \includegraphics[scale=0.08]{problem2.png}
\end{center}

\newpage

\section*{Problem 3}

In this problem, assume that the components of a DFA are given to you in appropriate data structures, that is, sets for $Q$, $\Sigma$, and $F$ and a map (dictionary) for $\delta$.

\begin{enumerate}[label=(\alph*)]
    \item Describe a method, i.e., an algorithm, which, given a DFA $M = (Q, \Sigma, \delta, q_0, F)$, determines whether $L(M) = \emptyset$.
    
    \item Describe a method, i.e., an algorithm, which, given two DFAs $M_1$ and $M_2$, determines whether their languages are disjoint, that is, whether $L(M_1) \cap L(M_2) = \emptyset$.
\end{enumerate}

\bigskip

\textbf{Answers:}

(a) I am not the greatest at pseudocode, so I am going to just describe this algorithm in English to the best of my ability.

First, we make an empty set---let's call it \texttt{visited}---to keep track of states that have been visited. Then we create a stack and push the initial state $q_0$. While the stack is not empty, we pop a state $q$ from the stack. Then, if $q \in F$ (accepting state), return \texttt{False} (because $L(M)$ is \textbf{not} empty). If $q$ is not in \texttt{visited}, add $q$ to \texttt{visited}, then for each symbol $a \in \Sigma$, we compute the next state $q' = \delta(q, a)$. If $q'$ is not in \texttt{visited}, we push $q'$ onto the stack. If the loop ends and no accepting state has been reached, we return \texttt{True} (indicating that $L(M) = \emptyset$).

\medskip

(b) Here we are determining whether the languages recognized by two DFAs are disjoint. First, we can make a new DFA that tracks the states of both DFAs at the same time. The new DFA starts in a state where both DFA 1 and DFA 2 are in their starting states. For every character we read, we move both DFAs according to their own rules.

The new machine is accepting if both DFAs are in accepting states. If we can reach any accepting state in this combined machine, it means at least one string is accepted by both DFA 1 and 2, meaning they aren't disjoint. We would then need to check all states that we can reach in this new DFA, and keep track of visited states. If we find a state that accepts for our new DFA, $L(M_1) \cap L(M_2) \neq \emptyset$ (the languages are not disjoint). If none exist, $L(M_1) \cap L(M_2) = \emptyset$ (the languages are disjoint).

\newpage

\section*{Problem 4}

Suppose $L_1$ and $L_2$ are both regular languages and that $L_2 \subseteq L_1$. Show that the language $L_3 = \{w \mid w \in L_1$ but $w \notin L_2\}$ is regular.

\bigskip

\textbf{Answer:}

\textbf{Yes}, it is regular.

As previously mentioned in the textbook, regular languages can be expressed using regex, finite automata, or grammars. $L_3$ has all strings that are in $L_1$ but not $L_2$. Since $L_2$ is regular, we can make a language that includes all the strings that are \textbf{NOT} in $L_2$. This new language is also regular because taking the complement keeps a language regular.

Now we can take the strings in $L_1$ and check them against our new language---the complement of $L_2$. When we combine $L_1$ with the complement of $L_2$ (finding strings that are both in $L_1$ and not in $L_2$) we are performing an intersection. Since both $L_1$ and the complement of $L_2$ are regular languages, their intersection is also a regular language. Again, taking the union, finding the intersection, and taking the complement keep languages regular if they're already regular---they're closed under those operations.

\newpage

\section*{Problem 5}

In this problem, $\Sigma = \{a, b\}$. For each of the following languages, give three examples of strings in the language and find a regular expression for the language.

\begin{enumerate}[label=(\alph*)]
    \item $L_1 = \{w \mid |w|$ is a multiple of $3\}$
    
    \item $L_2 = \{w \mid |w| \geq 3$ and $|w|$ is a multiple of $3$ and (if $w$ is long enough) the $4$th, $7$th, and every third letter after the $7$th letter of $w$ is the same as the first letter$\}$ (So, e.g., $abbaababaabb \in L_2$)
\end{enumerate}

\bigskip

\textbf{Answer:}

(a) Three examples could be $aaa$ (length $3$), $bbb$ (length $3$), and $abbbaa$ (length $6$). To form a regular expression for this language we need a group of $3$ symbols repeated any number of times. It could be either $a$ or $b$ for any of these. So the regular expression could be $((a \mid b)(a \mid b)(a \mid b))*$. I think we could also shorten this to $((a \mid b)^3)^*$.

\medskip

(b) This language has strings that are a multiple of $3$ like the last one, but also at least $3$ characters in the string, and if it is at least $7$ characters long then the $4$th, $7$th, and every $3$rd letter after the $7$th must match the first letter of the string.

Some examples could be $aaa$ (length $3$), $aaabbb$ (length $6$), and $abbbaa$ (length $6$).

Regular expressions can’t really remember characters, but we only have two possible characters, so we can split the regex into two cases.

Case 1 is that the first letter is $a$, and case 2 is that the first letter is $b$.

For case 1:

\[
a(a \mid b)(a \mid b)(a(a \mid b)(a \mid b))^*
\]

and for case 2:

\[
b(a \mid b)(a \mid b)(b(a \mid b)(a \mid b))^*
\]

Then we can combine both cases. So, the regexp is:

\[
(a(a \mid b)(a \mid b)(a(a \mid b)(a \mid b))^*) \mid (b(a \mid b)(a \mid b)(b(a \mid b)(a \mid b))^*)
\]

\newpage

\section*{Problem 6}

Let \(L \subseteq \Sigma^\ast\) and define \(P(L)\), the prefix-language of \(L\), as

\[
P(L) = \{w \in \Sigma^\ast \mid x = w y \text{ for some } x \in L, y \in \Sigma^\ast\}
\]

Show that if \(L\) is regular, then \(P(L)\) is also regular.

\bigskip

\textbf{Answer:}

If \(L\) is a regular language, then its prefix language \(P(L)\) is also regular.

\textbf{Proof:}

Since \(L\) is regular, there exists a deterministic finite automaton (DFA) \(M = (Q, \Sigma, \delta, q_0, F)\) that recognizes \(L\).

To construct a DFA \(M'\) that recognizes \(P(L)\):

1. \textbf{Use the same states and transitions} as \(M\):
   - \(M' = (Q, \Sigma, \delta, q_0, F')\).
   - The start state \(q_0\) and transition function \(\delta\) remain unchanged.

2. \textbf{Define the new set of accepting states} \(F'\):
   - \(F'\) consists of all states that can reach an accepting state in \(M\):
     \[
     F' = \{ q \in Q \mid \text{There exists a path from } q \text{ to some } f \in F \}
     \]
   - These are states from which some continuation leads to acceptance in \(M\).

The DFA \(M'\) accepts exactly those strings that are prefixes of strings in \(L\):

- For any \(w \in P(L)\), there exists \(y\) such that \(w y \in L\).
- In \(M'\), reading \(w\) leads to a state \(q \in F'\) because \(q\) can reach an accepting state in \(M\) via some \(y\).
- Conversely, if \(M'\) accepts \(w\), then there is a path from \(q_0\) to some \(q \in F'\) reading \(w\), and since \(q\) can reach an accepting state in \(M\), there exists \(y\) such that \(w y \in L\).

\textbf{Conclusion:}

Since \(M'\) is a DFA recognizing \(P(L)\), and regular languages are closed under DFA recognition, \(P(L)\) is regular.


\bigskip

\begin{center}
    \includegraphics[scale=0.08]{problem6.png}
\end{center}

\newpage

\section*{Problem 7}

Let $\Sigma = \{a, b\}$.

\begin{enumerate}[label=(\alph*)]
    \item Find a simple nondeterministic finite automaton accepting $(a \cup b)^\ast aab$.
    
    \item Convert the NFA of part (a) to a DFA by the method in Sipser. Provide only the portion of the DFA that's reachable from the start state.
\end{enumerate}

\bigskip

Here is the NFA:

\begin{center}
    \includegraphics[scale=0.08]{problem7a.jpg}
\end{center}

\bigskip

Here is the DFA:

\begin{center}
    \includegraphics[scale=0.08]{problem7b.jpg}
\end{center}

\newpage

\section*{Problem 8}

Let $A$ be an infinite regular language. Show that $A$ can be split into two infinite disjoint regular subsets.

\bigskip

\textbf{Answer:}

Since $A$ is a regular language, there exists a DFA $M = (Q, \Sigma, \delta, q_0, F)$ that recognizes $A$. Since $A$ is infinite but the DFA has finitely many states, by the pigeonhole principle, there must be cycles in $M$. Specifically, there is at least one loop on some path from the start state to an accepting state in $F$. We can use this cycle to generate infinitely many accepted strings by traversing the loop multiple times.

So, we can define two subsets $A_1$ and $A_2$ based on the number of times the loop is traversed (e.g., even vs. odd). So, we need to show that $A_1$ and $A_2$ are infinite, disjoint, and regular. This proof is a bit long, so I apologize if it's not very concise.

Let's consider the minimal DFA $M = (Q, \Sigma, \delta, q_0, F)$ that recognizes the infinite regular language $A$. Since $A$ is infinite and $M$ has a finite number of states, there must be at least one cycle in $M$.

There exists a state $q \in Q$ and a non-empty string $w \in \Sigma^+$ such that:

\[
\delta(q, w) = q \quad \text{(meaning $w$ forms a loop at state $q$)}
\]

There is a path from the start state $q_0$ to $q$ over some string $u \in \Sigma^\ast$.

There is a path from $q$ to an accepting state in $F$ over some string $v \in \Sigma^\ast$.

Using the identified cycle:

Set $A_1$:

\[
A_1 = \{u w^{2n} v \mid n \geq 0\}
\]

This set contains strings where the cycle $w$ is traversed an \textbf{even} number of times.

Set $A_2$:

\[
A_2 = \{u w^{2n+1} v \mid n \geq 0\}
\]

This set contains strings where the cycle $w$ is traversed an \textbf{odd} number of times.

Since $n \geq 0$ can be any non-negative integer, and $w$ is a non-empty string, both $A_1$ and $A_2$ contain infinitely many strings by varying $n$.

Any string in $A_1$ has the form $u w^{2n} v$, where $w$ is repeated an even number of times.

Any string in $A_2$ has the form $u w^{2n+1} v$, where $w$ is repeated an odd number of times.

Since a number cannot be both even and odd simultaneously, the sets $A_1$ and $A_2$ are disjoint:

\[
A_1 \cap A_2 = \emptyset
\]

We can write regular expressions representing $A_1$ and $A_2$ because regular languages are closed under concatenation and Kleene star.

For $A_1$:

\[
u (w w)^* v
\]

This expression concatenates $u$, zero or more repetitions of $w w$ (even number of $w$), and $v$.

For $A_2$:

\[
u\, w\, (w w)^* v
\]

This expression concatenates $u$, one $w$, zero or more repetitions of $w w$ (maintaining an odd count), and $v$.

Finite automata for $A_1$ and $A_2$:

We can construct finite automata $M_1$ and $M_2$ for $A_1$ and $A_2$, respectively, by modifying $M$:

For $M_1$: Adjust the transitions to accept when the cycle $w$ is traversed an even number of times.

For $M_2$: Adjust the transitions to accept when the cycle $w$ is traversed an odd number of times.

These automata are finite and recognize regular languages.

Union of $A_1$ and $A_2$:

\[
A_1 \cup A_2 = \{u w^{n} v \mid n \geq 0\} \subseteq A
\]

Since $u$, $w$, and $v$ are fixed strings and $n$ ranges over all non-negative integers, $A_1 \cup A_2$ comprises all strings formed by traversing the cycle any number of times, which are in $A$.

Note that there may be other strings in $A$ not of this form; however, since $A$ is infinite, and $A_1$ and $A_2$ are infinite subsets of $A$, we have effectively split $A$ into two infinite disjoint regular subsets.

Therefore, any infinite regular language $A$ can be split into two infinite disjoint regular subsets $A_1$ and $A_2$.

\newpage

\section*{Problem 9}

Let $\Sigma = \{0, 1, +, =\}$ and

\[
\text{ADD} = \{ x + y = z \mid x, y, z \text{ are binary integers, and } z \text{ is the sum of } x \text{ and } y \}
\]

Show that $\text{ADD}$ is not regular.

\bigskip

\textbf{Answer:}

I'm going to prove this by contradiction. Let's assume $\text{ADD}$ is a regular language. Since $\text{ADD}$ is regular, there exists a pumping length $p$ such that any string $s \in \text{ADD}$ with $|s| \geq p$ can be divided into three parts ($s = xyz$) satisfying:

\begin{itemize}
    \item $|xy| \leq p$
    \item $|y| \geq 1$
    \item For all $i \geq 0$, $x y^i z \in \text{ADD}$
\end{itemize}

Let

\[
s = 1^p + 1 = 1 0^p
\]

Here, $s$ represents the equation where $x = 1^p$, $y = 1$, and $z = 1 0^p$. This represents the sum $(2^p - 1) + 1 = 2^p$.

Since $|xy| \leq p$ and $|y| \geq 1$, the string $y$ must consist of at least one '1' from the first operand. So $y$ is a substring of the initial sequence of $1$s.

Now, pump down (i.e., take $i = 0$):

Remove $y$ to get $s' = x z$. The new first operand becomes $1^{p - |y|}$. The rest of $s$ remains unchanged.

Original equation:

\[
1^p + 1 = 1 0^p \quad \text{represents} \quad (2^p - 1) + 1 = 2^p
\]

Pumped-down equation:

\[
1^{p - |y|} + 1 = 1 0^p \quad \text{represents} \quad (2^{p - |y|} - 1) + 1 = 2^p
\]

Simplifies to:

\[
2^{p - |y|} = 2^p
\]

Which is false unless $|y| = 0$, but $|y| \geq 1$.

Therefore, $s' \notin \text{ADD}$, which contradicts the pumping lemma.

The assumption that $\text{ADD}$ is regular must be false.

Hence, $\text{ADD}$ is \textbf{not} a regular language.

\end{document}


Grade this exam. Go through every problem and tell if its right or wrong and why.