연습장 문서 원본 보기

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

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

Hence, there exists a unique natural number <math>n</math> with the desired property.

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

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

Hence, there is the a unique empty string <math>w</math> s.t. <math>|w| = 0</math>, and we can define <math>\epsilon</math> as the empty string <math>w</math>

==Ex. 3==
Let <math>w</math> be any string over an <math>\Sigma</math>.<br>
Existence)<br>
By the definition of <math>w</math>, <math>w</math> is defined at any position i s.t. <math>(i \in \mathbb{N}) \land (i \in |w|)</math>.<br>
Therefore, if <math>i < |w| </math>, then <math>\exist x \in \Sigma. (i,x)\in w</math>.

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

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

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

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

Thus, for every <math>x \in \Sigma</math>, there exists a unique string <math>w</math> s.t. <math>|w|=1</math> and <math>w</math>@<math>0=x</math>.

==Ex. 5==
<math>uv = \{(i,x)|(i,x)\in u\} \cup \{(</math><math>|</math><math>u</math><math>|</math><math>+j,y)|(j,y)\in v\}</math>

==Ex. 6==
(a)<br>
Let <math>\epsilon = \empty</math>.<br>
By the definition, <math>u\epsilon = \{(i,x)|(i,x)\in u\} \cup \{(</math><math>|</math><math>u</math><math>|</math><math>+j,y)|(j,y)\in \empty\} = \{(i,x)|(i,x)\in u\} \cup \empty = \{(i,x)|(i,x)\in u\} = u</math><br>
In the same way, <math>\epsilon u = \{(i,x)|(i,x)\in \empty\} \cup \{(</math><math>|</math><math>\empty</math><math>|</math><math>+j,y)|(j,y)\in u\} = \empty \cup \{(j,y)|(j,y)\in u\} = \{(j,y)|(j,y)\in u\} = u</math>

(b)<br>

<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>