--- date: '2024-02-16' description: assignment on deterministic and non-deterministic finite automata, regular language properties, product construction, and subset construction. id: A1 modified: 2026-06-05 15:08:39 GMT-04:00 seealso: - '[[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/sol.pdf|solutions]]' tags: - sfwr2fa3 title: DFAs, NFAs, and regular languages created: '2024-02-16' published: '2024-02-16' pageLayout: default slug: thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/A1 permalink: https://aarnphm.xyz/thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/A1.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## Q1. For each statement below, state if it is true or false, and explain why. The explanation does not need to be a formal proof, but the argument should be sound. > \[!question\] Statement a > > If $L_1$ is regular and $|L_1| = k$ and $L_2$ is non-regular, then $L_1 \cap L_2$ is regular. This statement is **false**. All finite languages are regular. $|L_1| = k$ implies that $L_1$ is finite, and therefore regular. The intersection of a regular language and a non-regular language is not guaranteed to be regular. Note that all string under $L_1 \cap L_2$ must be a subset of $L_1$, and a subset of a finite language is finite, therefore regular. For example, let $L_1$ be a regular language that contains a string $a^nb^n$ and $L_2 = \{a^nb^n\}$. The intersection of $L_1 \cap L_2$ is non-regular. > \[!question\] Statement b > > If $L_1$ and $L_2$ are non-regular, then $L_1 \cup L_2$ is regular. This statement is **false**. The union of a regular and a non-regular language is not guaranteed to be regular. A language is regular if there is an finite automaton that accepts it. Note that $L_1$ is a regular language, therefore finite, and $L_2$ is non-regular, therefore there does not exist a finite automaton that accepts it. If $L_1 \cup L_2$ is regular, then there must exist a finite automaton that accepts it. However, such automaton would also accept $L_2$ since $L_2 \subseteq L_{1} \cup L_2$, therefore meet contradiction. Which renders the statement **false**. > \[!question\] Statement c > > $\forall L_1 \mid L_1 \text{ :non-regular, } \exists L_2 \mid L_2 \text{ :regular} \land L_{1} \subseteq L_{2}$ This statement is **true**. Let $\Sigma$ be the alphabet of $L_1$., choose $L_2 = \Sigma^{*}$, which is regular. Since $\Sigma^{*}$ is the set of all strings formed from $\Sigma$ plus empty string, it is guaranteed to contain $L_1$. Therefore $L_1 \subseteq \Sigma^{*}$. Therefore, $L_1 \subseteq L_2$ ## Q2. Create a DFA $M$ such that: > \[!question\] Statement a > > M accepts all strings which begin with $b$ but do not contain the substring $bab$. ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_2a.svg]] > \[!question\] Statement b > > $\mathcal{L}{(M)} = \lbrace a^ib^jc^k \mid i+j+k \text{ is a multiple of 3} \rbrace$, $\Sigma = \lbrace a,b,c \rbrace$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_2b.svg]] > \[!question\] Statement c > > $\mathcal{L}{(M)} = \lbrace x \mid \text{at least two a\unicode{x2019}s in last three characters of x} \rbrace$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_2c.svg]] ## Q3. Via product construction, create a DFA $M$ such that $$ \mathcal{L}(M) = \{ a^n b^m \mid n \lor m \text{ is a multiple of 3} \} $$ First create two machine: one where $n$ is a multiple and one where $m$ is a multiple of 3. Then create the “union” machine: $$ \begin{align*} \mathcal{L}(M_1) &= \lbrace a^nb^m \mid n \text{ is a multiple of 3} \\\ \mathcal{L}(M_2) &= \lbrace a^nb^m \mid m \text{ is a multiple of 3} \end{align*} $$ First, we will construct $M_1$: ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_3a.svg]] Then, we will construct $M_2$: ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_3b.svg]] From product construction, we will create $M$ based on $M_1$ and $M_2$: ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_23.svg]] ## Q4. Create an NFA which accepts all string in which the third last character is an $a$. Then via subset construction, create an equivalent DFA. Show all your work _Solution_ We define the following NFA $(Q, \Sigma, \delta, q_0, F)$ with: - $Q = \{q_0, q_1, q_2, q_3, q_4\}$ - $\Sigma = \{a, b\}$ - Start state $q_0$ - Accept state $q_{3}$ - Transition function $\delta$ as follows: $$ \begin{align*} \delta(q_0, a) &= \{q_0, q_1\} \\\ \delta(q_0, b) &= \{q_0\} \\\ \delta(q_1, a) &= \{q_2\} \\\ \delta(q_1, b) &= \{q_2\} \\\ \delta(q_2, a) &= \{q_3\} \\\ \delta(q_2, b) &= \{q_3\} \\\ \delta(q_3, a) &= \{q_4\} \\\ \delta(q_3, b) &= \{q_4\} \\\ \delta(q_4, a) &= \{q_4\} \\\ \delta(q_4, b) &= \{q_4\} \end{align*} $$ Via subset construction, we can create the following DFA: Start state of DFA is $\{ q_0 \}$, as it is the epsilon closure of the start state of the NFA Transition table: | DFA state | $a$ | $b$ | | -------------------------------- | -------------------------------- | ------------------------- | | $\{q_{0}\}$ | $\{q_{0}, q_{1}\}$ | $\{q_{0}\}$ | | $\{q_{0}, q_{1}\}$ | $\{q_{0}, q_{1}, q_{2}\}$ | $\{q_{0},q_{2}\}$ | | $\{q_{0}, q_{2}\}$ | $\{q_{0}, q_{1}, q_{3}\}$ | $\{q_{0},q_{3}\}$ | | $\{q_{0}, q_{1}, q_{2}\}$ | $\{q_{0}, q_{1}, q_{2}, q_{3}\}$ | $\{q_{0}, q_{2}, q_{3}\}$ | | $\{q_{0}, q_{3}\}$ | $\{q_{4}\}$ | $\{q_{4}\}$ | | $\{q_{0}, q_{1}, q_{2}, q_{3}\}$ | $\{q_{4}\}$ | $\{q_{4}\}$ | | $\{q_{4}\}$ | $\{q_{4}\}$ | $\{q_{4}\}$ | The final state are any states that include $q_{3}$, which are $\{q_{0}, q_{1}, q_{2}, q_{3}\}$ and $\{q_{0}, q_{3}\}$. ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/rev1/a1/dfa_44.svg]] Where ```python dfa_states = { 'D0': '{q0}', 'D1': '{q0, q1}', 'D2': '{q0, q2}', 'D3': '{q0, q1, q2}', 'D4': '{q0, q3}', 'D5': '{q0, q1, q2, q3}', 'D6': '{q4}', } ```