연습장

Ex. 1

Existence)
Let [math]\displaystyle{ w }[/math] be any string over an [math]\displaystyle{ \Sigma }[/math].
By the definition, the domain of [math]\displaystyle{ w }[/math] is a finite initial segment of [math]\displaystyle{ \mathbb{N} }[/math].
This means that [math]\displaystyle{ \exist n \in \mathbb{N} }[/math] s.t. w is defined at [math]\displaystyle{ i \leftrightarrow i \lt n }[/math]

Uniquness)
Suppose that [math]\displaystyle{ \exist n,\,\, m }[/math] s.t. both satisfy the condition for the string [math]\displaystyle{ w }[/math].
That means, w is defined at position [math]\displaystyle{ i }[/math] if and only if [math]\displaystyle{ (i \lt n) \land (i \lt m) }[/math].
By definition, [math]\displaystyle{ \{i \in \mathbb{N}|i \lt n\} }[/math] and [math]\displaystyle{ \{i \in \mathbb{N}|i \lt m\} }[/math] are both domain of [math]\displaystyle{ w }[/math], which means they are same set.
So the only way that [math]\displaystyle{ \{i \in \mathbb{N}|i \lt n\} }[/math] and [math]\displaystyle{ \{i \in \mathbb{N}|i \lt m\} }[/math] are same is their endpoints are same. Therefore, [math]\displaystyle{ n = m }[/math].

Hence, there exists a unique natural number [math]\displaystyle{ n }[/math] with the desired property.

Ex. 2

Existence)
By definition, the domain of [math]\displaystyle{ w }[/math] is the finite initial segment of [math]\displaystyle{ \mathbb{N} }[/math].
If the domain is [math]\displaystyle{ \empty }[/math], then there is no position [math]\displaystyle{ i \in \mathbb{N} }[/math] where the [math]\displaystyle{ w }[/math] is defined.
In this situation, the length of the string [math]\displaystyle{ w }[/math] is 0.
Hence, there is a string [math]\displaystyle{ w }[/math] s.t. [math]\displaystyle{ |w| = 0 }[/math].

Uniquness)
Suppose that there is two sets [math]\displaystyle{ u,\,\, v }[/math] s.t. [math]\displaystyle{ |u| = 0,\,\, |v| = 0 }[/math].
Then [math]\displaystyle{ u,\,\, v }[/math] are not defined at any index, so both are empty relation, subset of [math]\displaystyle{ \mathbb{N} \times \Sigma }[/math].
So [math]\displaystyle{ u,\,\, v }[/math] are both empty, which means [math]\displaystyle{ u = v }[/math].

Hence, there is the a unique empty string [math]\displaystyle{ w }[/math] s.t. [math]\displaystyle{ |w| = 0 }[/math], and we can define [math]\displaystyle{ \epsilon }[/math] as the empty string [math]\displaystyle{ w }[/math]

Ex. 3

Let [math]\displaystyle{ w }[/math] be any string over an [math]\displaystyle{ \Sigma }[/math].
Existence)
By the definition of [math]\displaystyle{ w }[/math], [math]\displaystyle{ w }[/math] is defined at any position i s.t. [math]\displaystyle{ (i \in \mathbb{N}) \land (i \in |w|) }[/math].
Therefore, if [math]\displaystyle{ i \lt |w| }[/math], then [math]\displaystyle{ \exist x \in \Sigma. (i,x)\in w }[/math].

Uniquness)
By the definition of [math]\displaystyle{ w }[/math], relation [math]\displaystyle{ w \subseteq \mathbb{N} \times \Sigma }[/math] is partial function.
So there is only one output [math]\displaystyle{ x \in \Sigma }[/math] when i is given s.t. [math]\displaystyle{ i \lt |w| \land i \in \mathbb{N} }[/math].

Hence, For all strings [math]\displaystyle{ w }[/math] and for all [math]\displaystyle{ i \in \mathbb{N} }[/math], if [math]\displaystyle{ i \lt |w| }[/math], then there exists a unique [math]\displaystyle{ x \in \Sigma }[/math] s.t. [math]\displaystyle{ (i, x) \in w }[/math].

Ex. 4

Existence)
[math]\displaystyle{ |w| = 1 }[/math] means that the domain of [math]\displaystyle{ w }[/math] is [math]\displaystyle{ \{1\} }[/math].
So, let relation [math]\displaystyle{ w }[/math] be [math]\displaystyle{ w = \{(1, x)\} \subseteq \mathbb{N} \times \Sigma }[/math], s.t. [math]\displaystyle{ x \in \Sigma }[/math].
First, [math]\displaystyle{ w }[/math] is a partial function, since for the input 1, there is only one output value.
Second, the domain of [math]\displaystyle{ w }[/math] is [math]\displaystyle{ \{1\} }[/math], which is the finite initial segment of [math]\displaystyle{ \mathbb{N} }[/math]. Hence, there is [math]\displaystyle{ w }[/math] which satisfy given proposition.

Uniquness)
Suppose [math]\displaystyle{ u,\,\,v }[/math] are string, and [math]\displaystyle{ (|u|=|v|=1)\land (u }[/math]@[math]\displaystyle{ 0 = v }[/math]@[math]\displaystyle{ 0 = x, s.t. x \in \Sigma) }[/math] Then, the domain of both string is [math]\displaystyle{ \{1\} }[/math], and the alphabet corresponding to index 0 is [math]\displaystyle{ x }[/math] for both string. Hence, [math]\displaystyle{ u = v = \{(1, x)\} }[/math].

Thus, for every [math]\displaystyle{ x \in \Sigma }[/math], there exists a unique string [math]\displaystyle{ w }[/math] s.t. [math]\displaystyle{ |w|=1 }[/math] and [math]\displaystyle{ w }[/math]@[math]\displaystyle{ 0=x }[/math].

Ex. 5

[math]\displaystyle{ uv = \{(i,x)|(i,x)\in u\} \cup \{( }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ u }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ +j,y)|(j,y)\in v\} }[/math]

Ex. 6

(a)
Let [math]\displaystyle{ \epsilon = \empty }[/math].
By the definition, [math]\displaystyle{ u\epsilon = \{(i,x)|(i,x)\in u\} \cup \{( }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ u }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ +j,y)|(j,y)\in \empty\} = \{(i,x)|(i,x)\in u\} \cup \empty = \{(i,x)|(i,x)\in u\} = u }[/math]
In the same way, [math]\displaystyle{ \epsilon u = \{(i,x)|(i,x)\in \empty\} \cup \{( }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ \empty }[/math][math]\displaystyle{ | }[/math][math]\displaystyle{ +j,y)|(j,y)\in u\} = \empty \cup \{(j,y)|(j,y)\in u\} = \{(j,y)|(j,y)\in u\} = u }[/math]

(b)

[math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]