date: 2024-10-04
title: TOC-As-1
status: DONE
author:
  - AllenYGY
tags:
  - Assignment
  - TOC
publish: True

TOC-As-1

Question 1

.

Construct a counting procedure as below:

Each pair corresponds to a unique natural number.
Therefore is countalbe

.

Case I

If is a finite set with element;

Then which is finite. Therefore is countable.

Case 2

If is a infinite and countable set;
Then there must be a bijection between and .

And for 2 countable sets , is also a countable set.

For any element , we can write and for some .

Therefore, corresponds to the pair , which in turn corresponds to the natural number pair .

To establish a one-to-one correspondence, we can use a pairing function that maps each pair to a unique natural number k .

Therefore, is countable.

Since n times.

And is countable.

Therefore is countable.

Solution:

Solution

is uncountable.

Suppose a real number denote as . Then we build the table as below:

Index		Digits
0
1
2

Next we define a real number such that
. We can see a xis not in the list!

and are different at digit 0.
and are different at digit 1.
and are different at digit 2.
and are different at digit 3.

Thus, is not counted and set of reals in (0, 10) is uncountable.

is uncountable

Assume that the set of functions from to is countable.

Suppose all such functions can be listed as .

Define a function such that .
This ensures that differs from each at least at position .

Since is not equal to any in the list, this contradicts the assumption that we have listed all possible functions.

Therefore, the set of functions from to is uncountable.

Question 2

Prove the followings.(1 pt for each)

a

b

Two sets are isomorphic if they are of the same cardinality. Prove that the number of DFA's (without specifying ) is countable up to set isomorphism.

Question 3

Let Construct a DFA for each of the following languages. (10 pt for each)

a.

Current State

b.

Current State

c.

Current State

d. A run in a string is a substring of length at least one and consisting entirely of the same symbol. For example, has four runs: .

Current State

Question 4

Let be an arbitrary DFA. We construct a new DFA as . We need to prove that .

Note:

is the set difference.
is the set complement.

The goal is understood as set equality.
Thus, we need to prove , .

()
Assume .
Then .
Thus, DFA rejects .
In other words, DFA halts on a non-final state by consuming all symbols in .
By the construction of , is a final state of .
Thus, accepts , and .

()
Assume .
DFA accepts .
In other words, DFA halts on a final state by consuming all symbols in .
By the construction of , is a non-final state of .
Thus, rejects , so .
Thus, .
.