date: 2024-10-04
title: TOC-As-1
status: DONE
author:
- AllenYGY
tags:
- Assignment
- TOC
publish: True
TOC-As-1
Construct a counting procedure as below:
Each pair corresponds to a unique natural number.
Therefore
If
Then
If
Then there must be a bijection between
And for 2 countable sets
For any element
Therefore,
To establish a one-to-one correspondence, we can use a pairing function that maps each pair
Therefore,
Since
And
Therefore
Solution:
Suppose a real number
Index | Digits | |
---|---|---|
0 | ||
1 | ||
2 | ||
Next we define a real number
Thus,
Assume that the set of functions from
Suppose all such functions can be listed as
Define a function
This ensures that
Since
Therefore, the set of functions from
Prove the followings.(1 pt for each)
Two sets are isomorphic if they are of the same cardinality. Prove that the number of DFA's (without specifying
Let
Current State | ||
---|---|---|
Current State | ||
---|---|---|
Current State | ||
---|---|---|
Current State | ||
---|---|---|
Let
Note:
The goal
Thus, we need to prove
(
Assume
Then
Thus, DFA
In other words, DFA
By the construction of
Thus,
(
Assume
DFA
In other words, DFA
By the construction of
Thus,
Thus,