---
date: '2025-03-17'
description: and assignment 2.
id: A2
modified: 2026-06-05 15:08:39 GMT-04:00
tags:
- sfwr2fa3
title: Regex and quotient construction
created: '2025-03-17'
published: '2025-03-17'
pageLayout: default
slug: thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A2
permalink: https://aarnphm.xyz/thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A2.md
generator:
quartz: v4.6.0
hostedProvider: Cloudflare
baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
> \[!question\] Question 1
>
> Give regular expressions for the languages below
> $L = \{ a^n b^m \mid (n+m)\%2 = 0 \}$
$\boxed{(aa)^{*}(bb)^{*} + a(aa)^{*}b(bb)^{*}}$
> $L = \{ w \mid w \text{ does not contain the substring: } aba \}$
$\boxed{b^{*}a^{*}((bb)b^{*}a^{*})^{*}b^{*}}$
> $L = \{ w \mid w \text{ has an even number of } b's \}$
$\boxed{(a^{*}ba^{*}b)^{*} a^{*}}$
> \[!question\] Question 2
>
> Minimize the number of states in DFA via quotient construction.
![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a2/q2.webp]]
_Note that all newly marked notes will be highlighted yellow_.
Initial setup
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | | x | | | | | | |
| 5 | x | | | x | | | | | | |
| 6 | x | | | x | | | | | | |
| 7 | x | | | x | | | | | | |
| 8 | x | | | x | | | | | | |
| 9 | x | | | x | | | | | | |
Iteration 1:
- $(\delta (0,a), \delta (3,a)) = (1,4)$, which is unmarked, skipped
Iteration 2:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | -------------- | - | - | - | - | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | x | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | | x | | | | | | |
| 5 | x | x | | x | | | | | | |
| 6 | x | | | x | | | | | | |
| 7 | x | | | x | | | | | | |
| 8 | x | | | x | | | | | | |
| 9 | x | | | x | | | | | | |
- $(\delta (1,a), \delta (2,a)) = (2,3)$, which is marked, mark $(1,2)$
- $(\delta (1,a), \delta (4,a)) = (2,5)$, which is unmarked, skipped
- $(\delta (1,a), \delta (5,a)) = (2,0)$, which is marked, mark $(1,5)$
- $(\delta (1,a), \delta (6,a)) = (2,7)$, which is unmarked, skipped
- $(\delta (1,a), \delta (7,a)) = (2,9)$, which is unmarked, skipped
- $(\delta (1,a), \delta (8,a)) = (2,9)$, which is unmarked, skipped
- $(\delta (1,a), \delta (9,a)) = (2,7)$, which is unmarked, skipped
Iteration 3:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | -------------- | - | - | - | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | x | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | x | x | | | | | | |
| 5 | x | x | | x | | | | | | |
| 6 | x | | x | x | | | | | | |
| 7 | x | | x | x | | | | | | |
| 8 | x | | x | x | | | | | | |
| 9 | x | | x | x | | | | | | |
- $(\delta (2,a), \delta (4,a)) = (3,5)$, which is marked, mark $(2,4)$
- $(\delta (2,a), \delta (5,a)) = (3,0)$, which is unmarked, skipped
- $(\delta (2,a), \delta (6,a)) = (3,7)$, which is marked, mark $(2,6)$
- $(\delta (2,a), \delta (7,a)) = (3,9)$, which is marked, mark $(2,7)$
- $(\delta (2,a), \delta (8,a)) = (3,9)$, which is marked, mark $(2,8)$
- $(\delta (2,a), \delta (9,a)) = (3,7)$, which is marked, mark $(2,9)$
Iteration 4:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | -------------- | - | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | x | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | x | x | | | | | | |
| 5 | x | x | | x | x | | | | | |
| 6 | x | | x | x | | | | | | |
| 7 | x | | x | x | | | | | | |
| 8 | x | | x | x | | | | | | |
| 9 | x | | x | x | | | | | | |
- $(\delta (4,a), \delta (5,a)) = (5,0)$, which is marked, mark $(4,5)$
- $(\delta (4,a), \delta (6,a)) = (5,7)$, which is unmarked, skipped
- $(\delta (4,a), \delta (7,a)) = (5,9)$, which is unmarked, skipped
- $(\delta (4,a), \delta (8,a)) = (5,9)$, which is unmarked, skipped
- $(\delta (4,a), \delta (9,a)) = (5,7)$, which is unmarked, skipped
Iteration 5:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | -------------- | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | x | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | x | x | | | | | | |
| 5 | x | x | | x | x | | | | | |
| 6 | x | | x | x | | x | | | | |
| 7 | x | | x | x | | x | | | | |
| 8 | x | | x | x | | x | | | | |
| 9 | x | | x | x | | x | | | | |
- $(\delta (5,a), \delta (6,a)) = (0,7)$, which is marked, mark $(5,6)$
- $(\delta (5,a), \delta (7,a)) = (0,9)$, which is marked, mark $(5,7)$
- $(\delta (5,a), \delta (8,a)) = (0,9)$, which is marked, mark $(5,8)$
- $(\delta (5,a), \delta (9,a)) = (0,7)$, which is marked, mark $(5,9)$
Iteration 6:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - | - | - |
| 0 | | | | | | | | | | |
| 1 | x | | | | | | | | | |
| 2 | x | x | | | | | | | | |
| 3 | | x | x | | | | | | | |
| 4 | x | | x | x | | | | | | |
| 5 | x | x | | x | x | | | | | |
| 6 | x | | x | x | | x | | | | |
| 7 | x | | x | x | | x | | | | |
| 8 | x | | x | x | | x | | | | |
| 9 | x | | x | x | | x | | | | |
- $(\delta (6,a), \delta (7,a)) = (7,9)$, which is unmarked, skip
- $(\delta (6,a), \delta (8,a)) = (7,9)$, which is unmarked, skip
- $(\delta (6,a), \delta (9,a)) = (7,7)$, which is unmarked, skip
We stopped here, given that 7,8,9 doesn’t contains any direct transition on a to any final states.
The final transition table are as follows:
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - | - | - |
| 0 | | x | x | | x | x | x | x | x | x |
| 1 | x | | x | x | | x | | | | |
| 2 | x | x | | | x | | x | x | x | x |
| 3 | | x | x | | x | x | x | x | x | x |
| 4 | x | | x | x | | x | | | | |
| 5 | x | x | | x | x | | x | x | x | x |
| 6 | x | | x | x | | x | | | | |
| 7 | x | | x | x | | x | | | | |
| 8 | x | | x | x | | x | | | | |
| 9 | x | | x | x | | x | | | | |
We have the following states are equivalent:
- $1 \approx 4 \approx 6 \approx 7 \approx 8 \approx 9$
- $2 \approx 5$
Final DFA
![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a2/minimized-dfa.webp]]
> \[!question\] Question 3
>
> Your friend is looking at the formal definition of the pumping lemma and they think something is wrong
>
> $$
> L \text{ is regular } \implies (\exists k \mid k>0: (\forall x,y,z \mid xyz \in L \land |y| > k: ( \exists u,v,w \mid y=uvw \land v \neq \epsilon: (\forall i | i \geq 0: xuv^iwz \in L))))
> $$
>
> They understand the argument it is crafted around, that is, due to the fact that strings are arbitrarily long and a DFA has finite states there must be a segment of accepted strings which “loop” in the machine. However, they claim for the pumping lemma above to hold, $L$ must be infinite, because if $L$ was finite the argument about “looping” no longer holds. Therefore, the pumping lemma only holds when $L$ is infinite.
>
> You can see where your friend is coming from, but they are incorrect. Why? Be precise in your argument, that is, show how if $L$ is finite, then
>
> $$
> (\exists k \mid k > 0: (\forall x,y,z \mid xyz \in L \land |y| > k: ( \exists u,v,w \mid y=uvw \land v \neq \epsilon: (\forall i | i \geq 0: xuv^iwz \in L))))
> $$
>
> evaluate to true.
The Pumping lemma also **holds** for finite regular language as well.
We need to show that if we assume $L$ is finite, then the pumping lemma is True.
Now, there exists a longest string in L called $m$, choose $k^{'} = |m|$
Consider the “forall” section $\forall x,y,z \mid xyz \in L \land |y| >k$ is _False_:
- For any string $xyz \in L$ we know that $|xyz| \le m$ (since m is the longest string in $L$)
- since $y$ is a substring of $xyz$, we must have $|y| \le |xyz| \le m = k$
Given that the antecedent (“if” part) of an implication is false, the entire implication is vacuous truth (when the set is empty)
Therefore, the entire condition is true via vacuous truth (it holds trivially, as there are no strings $xyz \in L \mid |y| > k$)
> \[!question\] Question 4
>
> Using the Pumping Lemma, prove the following languages are not regular.
> $L = \{ a^{nm} b^{m} a^{n} \mid n,m \ge 0 \}$
1. The demon first pick $k=n=m$
2. Choose $x=a^{k^{2}}, y=b^{k}, z=a^{k}$
3. pick $u=b^{j},v=b^{r},w=b^{l}$ such that $j+r+l=k, r>0$
4. pick $s^{'} = xuv^{i}wz = a^{k^{2}}b^{j}(b^{r})^{i}b^{l}a^{k}$
use $i=2$ we have
$$
\begin{aligned}
s^{'}&=a^{k^{2}}b^{j}b^{2r}b^{l}a^{k} \\
&=a^{k^{2}}b^{r}b^{k}a^{k}
\end{aligned}
$$
5. That $s^{'} \notin L$, therefore $L$ is not regular
$\boxed{q.e.d}$
> $L = \{ww \mid w \in \Sigma^*\}$
1. The demon pick k
2. Choose $x=a^{k}b,y=a^{k},z=b$
3. pick $u=a^{j},v=a^{r},w=a^{l}$ such that $j+r+l=k, r>0$
4. pick $s^{'} = xuv^{i}wz = a^{k}ba^{j}(a^{r})^{i}a^{l}b$
use $i=2$ we have
$$
\begin{aligned}
s^{'}&=a^{k}ba^{j}a^{2r}a^{l}b \\
&=a^{k}ba^{r}a^{k}b
\end{aligned}
$$
5. That $s^{'} \notin L$, therefore $L$ is not regular
$\boxed{q.e.d}$
> $L = \{a^{k^{3} } \mid k \ge 0\}$
1. The demon pick k
2. Choose $x=z=\epsilon,y=a^{k^{3}}$
3. pick $u=a^{j},v=a^{r},w=a^{l}$ such that $j+r+l=k^{3}, r>0, j+r\le k$
4. pick $s^{'} = xuv^{i}wz = a^{j}(a^{r})^{i}a^{l}$
use $i=2$ we have
$$
\begin{aligned}
s^{'}&=a^{j}(a^{r})^{2}a^{l} \\
&=a^{k^{3}+r}
\end{aligned}
$$
We can prove that $k^{3} < k^{3}+r <(k+1)^{3}$
- Since $r>0$, we have $k^{3} k^{3} + k \ge k^{3}+r$
Therefore, $k^{3}+r$ cannot be a perfect cube
5. That $s^{'} \notin L$, therefore $L$ is not regular
$\boxed{q.e.d}$
> \[!question\] Question 5
>
> Give the CFGs for the following language
> $L = \{a^{n}b^{m}c^{k} \mid n \neq m + k\}$
$L = L_{1} \cup L_{2}$ where
- $L_{1} = \{a^{n}b^{m}c^{k} \mid n < m+k\}$
- $L_{2} = \{a^{n}b^{m}c^{k} \mid n > m+k\}$
Let grammar $G = (V, \Sigma, R, S)$ where:
- $V = \{S, S_{1}, S_{2}, A, B\}$ be set of variables
- $\Sigma = \{a,b,c\}$ be the set of terminals
$$
\begin{aligned}
S &\to S_{1} \mid S_{2} \\
S_{1} &\to aS_{1} \mid aA \\
A &\to aAb \mid B \\
B &\to aBc \mid \epsilon \\
S_{2} &\to S_{2}b | S_{2}c | C\\
C &\to aCb | D\\
D &\to aDc | \epsilon
\end{aligned}
$$
> $L=\{a^{n}b^{m}c^{k} \mid n = m+k\}$
$$
\begin{aligned}
S &\to aSc \mid U\\
U &\to aUb \mid \epsilon
\end{aligned}
$$