--- date: '2025-02-05' description: and assignment 1. id: A1 modified: 2026-06-05 15:08:38 GMT-04:00 tags: - sfwr2fa3 title: product construction and DFAs created: '2025-02-05' published: '2025-02-05' pageLayout: default slug: thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A1 permalink: https://aarnphm.xyz/thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A1.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## question 1. > \[!question\] a > > If $L_{1}$ is regular and $|L_{1}| = k$ and $L_{2}$ is non-regular, then $L_{1} \cap L_{2}$ is regular $\boxed{\text{True}}$ $L_{1} \cap L_{2} = L_{3}$ implies $L_{3} \subseteq L_{1}$ (intersection) Given that $|L_{1}| = k$, meaning there is a fixed number of string in $L_{1}$ ,therefore $L_{1}$ is finite. Given that all finite language are regular, $L_{1} \cap L_{2}$ will contain at-most $k$-string, making $L_{3}$ regular > \[!question\] b > > If $L_{1}$ is regular and $L_{2}$ is non-regular, then $L_{1} \cup L_{2}$ is regular $\boxed{\text{False}}$ If $L_{1} = \{ ab \}$ where it only accepts the string $ab$, and $L_{2} = \{ a^n b^n | n \geq 0 \}$, then $L_{1} \cup L_{2} = \{ a^n b^n | n \geq 0 \}$, which is non-regular > \[!question\] c > > $\forall L_{1}$ such that $L_{1}$ is a non-regular language, $\exists L_{2}$ such that $L_{2}$ is regular and $L_{1} \subseteq L_{2}$ $\boxed{\text{True}}$ For all non-regular languages $L_{1}$, they can be seen as a subset of $\Sigma^{*}$. Given that $\Sigma^{*}$ is regular (a DFA with one accepting state), this means the aforementioned statement holds. ## question 2. > \[!question\] a > > $M$ accepts all strings which begin with $b$ but do not contain the substring $bab$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/2a.webp]] > \[!question\] b > > $\mathcal{L}(M) = \{ a^i b^j c^k | i + j + k \text{ is a multiple of 3} \}, \Sigma = \{ a,b,c \}$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/2b.webp]] > \[!question\] c > > $\mathcal{L}(M) = \{ x \mid \text{ There are at least two a\unicode{x2019}s in the last three characters of } x \}$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/2c.webp]] ## question 3. Via production construction, create a DFA $M$ such that $$ \mathcal{L}(M) = \{ a^n b^m | \text{n or m is a multiple of 3} \} $$ $M_{1}$: ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/m1.webp]] $M_{2}$: ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/m2.webp]] | state | a | b | dangling | | ------ | ------ | ------ | -------- | | 0a | 1a | 3b | | | ~~0b~~ | ~~1e~~ | ~~3c~~ | | | ~~0c~~ | ~~1e~~ | ~~3d~~ | | | ~~0d~~ | ~~1e~~ | ~~3b~~ | | | 0e | 1e | 3e | ✅ | | 1a | 2a | 4b | | | ~~1b~~ | ~~2e~~ | ~~4c~~ | | | ~~1c~~ | ~~2e~~ | ~~4d~~ | | | ~~1d~~ | ~~2e~~ | ~~4d~~ | | | 1e | 2e | 4e | ✅ | | 2a | 0a | 4b | | | ~~2b~~ | ~~0e~~ | ~~4c~~ | | | ~~2c~~ | ~~0e~~ | ~~4d~~ | | | ~~2d~~ | ~~0e~~ | ~~4b~~ | | | 2e | 0e | 4e | ✅ | | ~~3a~~ | ~~4a~~ | ~~3b~~ | | | 3b | 4e | 3c | | | 3c | 4e | 3d | | | 3d | 4e | 3b | | | 3e | 4e | 3e | ✅ | | 4a | 4a | 4b | ✅ | | 4b | 4e | 4c | | | 4c | 4e | 4d | | | 4d | 4e | 4b | | | 4e | 4e | 4e | | _table 1: product construction of $\mathcal{L}(M) = \{ a^n b^m | \text{n or m is a multiple of 3} \}$_ _note: the state that are not used will be crossed out_ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/prod-construct-dfa.webp]] ## question 4. > \[!question\] Question > > NFA which accepts all string in which the third last character is an a. Then via subset construction create an equivalent DFA $\boxed{\text{NFA}}$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/nfa.webp]] | state | a | b | note | | ----- | ----------- | ----------- | -------------------- | | 0 | 01 | 0 | | | 1 | 2 | 2 | not connected in DFA | | 2 | 3 | 3 | not connected in DFA | | 3 | $\emptyset$ | $\emptyset$ | not connected in DFA | | 01 | 012 | 02 | | | 02 | 013 | 03 | | | 03 | 01 | 0 | | | 12 | 23 | 23 | not connected in DFA | | 13 | 2 | 2 | not connected in DFA | | 23 | 3 | 3 | not connected in DFA | | 012 | 0123 | 023 | | | 013 | 012 | 02 | | | 023 | 013 | 03 | | | 123 | 23 | 23 | not connected in DFA | | 0123 | 0123 | 023 | | _table 2: subset construction for given NFA_ $\boxed{\text{DFA}}$ ![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a1/subset-construct-dfa.webp]] ## question 5. > \[!question\] Question > > Create a sound argument that the concatenation of two regular languages is also regular. Specifically, if $L_{1}$ and $L_{2}$ are regular then $L_{1} L_{2}$ is also regular. > This does not need to be a formal proof, but the argument should be very convincing. > > _Hint_: if $L_{1}$ and $L_{2}$ are regular you can make “machines” for them; how would you make a “machine” for $L_{1} L_{2}$. Given $L_{1}$ and $L_{2}$ are both regular languages, there exists and DFA $M_{1}$ and $M_{2}$ that recgonize $L_{1}$ and $L_{2}$ respectively Let $M_{1} = (Q_{1}, \Sigma, \delta_1, q_{01}, F_{1})$ and $M_{2} = (Q_{2}, \Sigma, \delta_2, q_{02}, F_{2})$ We can try to construct a NFA $N$ to recognize $L_{1} L_{2}$, where we combine both states of $M_{1}$ and $M_{2}$ via product construction, then we add $\epsilon$-transition from every accepting state in $F_{1}$ to start state $q_{02}$ of $M_{2}$ Conceptually, for a string $w \in L_{1} L_{2}$, split $w = uv, u \in L_{1}, v \in L_{2}$ - If $N$ process $u$ in $M_{1}$, reach accept states $F_{1}$, then $\epsilon$ transition to $q_{02}$, then process $v$ in $M_{2}$, ending in $F_{2}$ - if no valid splits, then it rejects the string - for empty string: if $\epsilon \in L_{1}$ then it can transition to $M_{2}$, and vice versa. Given that regular language are also closed under NFAs, if we can build a NFA which proves that $L_{1} L_{2}$ is regular $\boxed{\text{q.e.d}}$