CFG, and Turing machines.

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 \}$

2

Turing machines with carry-bit

Note that all TODOs are replaced with $\boxed{\text{answers}}$

Table 1

Table 2

Table 3

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

If we enumerate $\mathbb{N}^3$, we can applying the pairing extension twice. Meaning

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}}$