---
date: '2025-04-08'
description: and assignment 3
id: A3
modified: 2026-06-05 15:08:39 GMT-04:00
tags:
- sfwr2fa3
title: CFG, and Turing machines.
created: '2025-04-08'
published: '2025-04-08'
pageLayout: default
slug: thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A3
permalink: https://aarnphm.xyz/thoughts/university/twenty-four-twenty-five/sfwr-2fa3/A3.md
generator:
quartz: v4.6.0
hostedProvider: Cloudflare
baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
> \[!question\] 1
>
> Let
>
> $$
> L_{1} = \{ a^n b^m c^k | n,m,k \geq 0 \}
> $$
>
> and
>
> $$
> L_{2} = \{ a^n b^n c^n | n \geq 1 \}
> $$
>
> Complete the following PDA such that $L(M) = L_{1} - L_{2}$ where $\Sigma = \{ a, b, c \}$
![[thoughts/university/twenty-four-twenty-five/sfwr-2fa3/a3/q1.webp]]
> \[!question\] 2
>
> Turing machines with _carry-bit_
_Note that all TODOs are replaced with $\boxed{\text{answers}}$_
| | 1 | 0 | x | # | c | $\square$ |
| -------------------- | --------------------------------- | --------------------------------- | ---------------------------------------- | ---------------------------------- | ---------------------------------------- | ------------------------------------------------ |
| $q_s$ | $(q_{1,1}, \text{x}, \text{R})$ | $(q_{1,3}, \text{x}, \text{R})$ | $(q_s, \text{x}, \text{R})$ | - | - | - |
| $q_{1,1}$ | $(q_{1,1},1,\text{R})$ | $(q_{1,1},0,\text{R})$ | - | $(q_{1,2}, \#, \text{R})$ | - | - |
| $q_{1,2}$ | $(q_{1,5},\text{x},\text{R})$ | $\boxed{(q_{1,6}, x, \text{R})}$ | $(q_{1,2}, \text{x}, \text{R})$ | - | - | - |
| $q_{1,3}$ | $(q_{1,3},1,\text{R})$ | $(q_{1,3},0,\text{R})$ | - | $(q_{1,4}, \#, \text{R})$ | - | - |
| $q_{1,4}$ | $\boxed{(q_{1,6}, x, \text{R})}$ | $(q_{1,7},\text{x},\text{R})$ | $(q_{1,4}, \text{x}, \text{R})$ | - | - | - |
| $q_{1,5}$ | $(q_{1,5},1,\text{R})$ | $(q_{1,5},0,\text{R})$ | - | $(q_{1,8},\#,\text{R})$ | - | - |
| $q_{1,6}$ | $(q_{1,6},1,\text{R})$ | $(q_{1,6},0,\text{R})$ | - | $(q_{1,9},\#,\text{R})$ | - | - |
| $q_{1,7}$ | $(q_{1,7},1,\text{R})$ | $(q_{1,7},0,\text{R})$ | - | $(q_{1,10},\#,\text{R})$ | - | - |
| $q_{1,8}$ | $\boxed{(q_{1,8}, 1, \text{R})}$ | $\boxed{(q_{1,8}, 0, \text{R})}$ | - | - | $\boxed{(q_{1,8}, c, R)}$ | $\boxed{(q_{1,\text{end}_1},\text{c},\text{L})}$ |
| $q_{1,9}$ | $\boxed{(q_{1,9}, 1, \text{R})}$ | $\boxed{(q_{1,9}, 0, \text{R})}$ | - | - | $\boxed{(q_{1,9}, c, R)}$ | $\boxed{(q_{1,\text{end}_1}, 1,\text{L})}$ |
| $q_{1,10}$ | $\boxed{(q_{1,10}, 1, \text{R})}$ | $\boxed{(q_{1,10}, 0, \text{R})}$ | - | - | $\boxed{(q_{1,10}, c, R)}$ | $\boxed{(q_{1,\text{end}_1}, 0,\text{L})}$ |
| $q_{1,\text{end}_1}$ | $(q_{1,\text{end}_1},1,\text{L})$ | $(q_{1,\text{end}_1},0,\text{L})$ | - | $(q_{1,\text{end}_2},\#,\text{L})$ | $(q_{1,\text{end}_1},\text{c},\text{L})$ | - |
| $q_{1,\text{end}_2}$ | $(q_{1,\text{end}_3},1,\text{L})$ | $(q_{1,\text{end}_3},0,\text{L})$ | $(q_{1,\text{end}_2},\text{x},\text{L})$ | $(q_{1,\text{end}_2},\#,\text{L})$ | - | $(q_{2,s},\square,\text{R})$ |
| $q_{1,\text{end}_3}$ | $(q_{1,\text{end}_3},1,\text{L})$ | $(q_{1,\text{end}_3},0,\text{L})$ | $(q_{1,\text{end}_3},\text{x},\text{L})$ | $(q_{1,\text{end}_3},\#,\text{L})$ | - | $(q_s,\square,\text{R})$ |
_Table 1_
| | 1 | 0 | x | # | c | $\square$ |
| --------- | ------------------------- | ------------------------- | ------------------------------- | ------------------------------- | ------------------------- | ------------------------------ |
| $q_{2,s}$ | - | - | $\boxed{(q_{2,s}, \square, R)}$ | $\boxed{(q_{2,1}, \square, R)}$ | - | - |
| $q_{2,1}$ | - | - | $\boxed{(q_{2,1}, \square, R)}$ | $\boxed{(q_{2,2}, \square, R)}$ | - | - |
| $q_{2,2}$ | $\boxed{(q_{2,2}, 1, R)}$ | $\boxed{(q_{2,2}, 0, R)}$ | - | - | $\boxed{(q_{2,2}, c, R)}$ | $(q_{3,s}, \square, \text{L})$ |
_Table 2_
| | 1 | 0 | c | $\square$ | Notes |
| --------- | ------------------------- | ------------------------- | ------------------------- | ------------------------ | ------------- |
| $q_{3,s}$ | $\boxed{(q_{3,s}, 1, L)}$ | $\boxed{(q_{3,s}, 0, L)}$ | $\boxed{(q_{3,1}, 0, L)}$ | $\boxed{End}$ | no carry over |
| $q_{3,1}$ | $\boxed{(q_{3,1}, 0, L)}$ | $\boxed{(q_{3,s}, 1, L)}$ | $\boxed{(q_{3,1}, 1, L)}$ | $(q_{3,s}, 1, \text{L})$ | carry over |
_Table 3_
> \[!question\] 3
>
> Let $\mathbb{N}^3 = N \times N \times N$. For example, (1, 5, 6), (0, 999, 124115), and (10, 10, 10) are all elements of $\mathbb{N}^3$. Prove $\mathbb{N}^3$ is countably infinite. Hint: find a way to enumerate it. \[10\]
To prove that $\mathbb{N}^3$ is countably infinite, we will prove there _exists a bijection_ $f: \mathbb{N} \to \mathbb{N}^3$
We can enumerate $\mathbb{N}^3$ lexicographically by ordering the set $\{T_{0}, T_{1}, T_{2}, \ldots \}$ sequentially.
- $T_{0} = \{(0, 0, 0)\}$
- $T_{1} = \{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}$
- $T_{2} = \{(2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2)\}$
Via Cantor Pairing function, we have the following bijection $f: \mathbb{N}^2 \to \mathbb{N}$ where
$$
f(x, y) = \frac{(x+y)(x+y+1)}{2} + y
$$
If we enumerate $\mathbb{N}^3$, we can applying the pairing extension twice. Meaning
$$
g(x, y, z) = f(x, f(y, z))
$$
This bijection is:
- injective: given that $f$ is a bijection between $\mathbb{N}^2 \to \mathbb{N}$, each $(y, z)$ pair maps to unique value $f(y, z)$. Therefore each $(x, f(y, z))$ pair maps to a unique natural numbers. Therefore different triples $(x, y, z)$ maps to a different natural numbers
- surjective: for any $n \in \mathbb{N}$ we can find unique values $a,b \in \mathbb{N}$ such that $f(a, b) = n$ (via inverse of $f$) Therefore for $b$, we can find a unique value $c, d \in \mathbb{N}$ such that $f(c,d) = b$. This means $n = g(a,c, d)$ ,therefore every natural number is in the range of $g$
$\boxed{\text{q.e.d}}$