Theory of computation (1)

본 내용은 KOCW 한양대학교 “오토마타 및 계산이론” 강좌 1강을 보며 정리한 내용입니다.

기호
1. alphabet

$\Sigma$라는 기호를 사용하며 symbol들의 집합을 의미합니다.

ex) $\Sigma = \{a, b\}$

$a,b$ 라는 symbol로 이루어져 있다.

2. string

alphabet 안에 있는 symbol들을 연결해서 만든 모든것

ex) $\Sigma = \{a, b\}$, $w = abab, aaabbbaa$

$w$ string 의 갯수는 무한개가 될수 이다.

• string concatenation
  • $w = a_1 a_2 \cdots a_n$, $v=b_1b_2 \cdots b_n$
  • $wv = a_1 a_2 \cdots a_nb_1b_2 \cdots b_n$

• reverse string

  • $w = a_1 a_2 \cdots a_n$
  • $w^R = a_n a_{n-1} \cdots a_1$

• length of string

  • $w = a_1 a_2 \cdots a_n$
  • $\mid w \mid= n$

• null string (길이가 0인 string)

  • $\mid \lambda \mid= 0$
• sub string (string의 일부)
  • $w = a b c\cdots wxyz$

  • prefix (맨 앞의 symbol에서 시작하는 string)

    • $w_{prefix} =a, ab, abc$

  • suffix (맨 뒤의 symbol로 끝나는 string)

    • $w_{suffix} =z, yz, xyz$

• $w^n$
  • $w$를 n개 concatenation 한것을 의미합니다
  • $w^0$ = $\lambda$ $\to$ $\mid w^0 \mid = 0$
  • $w^1$ = $w$
  • $w^2$ = $ww$
  • $w^n$ = $w \cdots w$

3. language

만약 $\Sigma=\{a,b\}$라고 한다면 가능한 모든 조합의 집합을 $\Sigma^{*}=\{\lambda, a, b, ab, aa, bb, aab, \cdots\}$ 라고 한다.

$\Sigma^+ = \Sigma^{*} - \{\lambda\}$ 로 정의합니다.

language는 $\Sigma^{*}$의 subset이라고 생각하면 됩니다.

ex) $L=\{a^n b^n ; n\geq0\}$

$a$가 $b$보다 앞에 있고, $a, b$의 갯수가 같은 모든 가능한 것을 language라고 할수 있다.

language안에 있는 string을 sentence라고 부릅니다. 즉 language는 sentence의 집합입니다.

• $L^R$ = $\{W^R : W \in L\}$
  • $L$ = $\{a^n b^n ; n\geq0\}$
  • $L^R$ = $\{b^n a^n ; n\geq0\}$

• $L_1 L_2$
  • $L_1$ = $\{a, aa\}$, $L_2$ = $\{b, bb\}$
  • $L_1 L_2$ = $\{ab, abb, aab, aabb\}$

• $L^n$= $L \cdots L$ : $L$을 $n$ 번 반복한것

  • $L$ = $\{a^n b^n ; n\geq0\}$

  • $L^0$ = $\{\lambda\} \neq \{\}$

  • $L^2$ = $\{a^n b^n a^m b^m; n\geq0, m\geq0\}$

• $L^*$
  • $L^*$ = $L^0 \cup L^1 \cup L^2 \cdots $
• $L^+$
  • $L^*$ = $L^1 \cup L^2 \cup L^3 \cdots $

문법(Grammer)

$G = (V, T, S, P)$

• V : Variables
• T : terminal symbols
• S : start variable
• P : productions

이해를 하기 위해 바로 예를 들어 보겠습니다.

G = $(\{S\}, \{a,b\}, S, P)$

production rule $P$는 다음과 같이 정의하였습니다.

$$S\to aSb$$ $$S \to \lambda$$

production rule에 의해 변형하는 것을 derivation이라고 합니다. derivation은 다음과 같이 할수 있습니다

$S \Rightarrow aSb \Rightarrow ab$

terminal symbols로 이루어지면 sentence라고 하며, sentence 전을 sentential form이라고 합니다.

위의 예에서 sentence는 $ab$이며, sentential form은 $aSb$ 입니다. 또 다른 예를 들어보겠습니다

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$

위의 예에서 sentence는 $aabb$이며, sentential form은 $aaSbb$ 입니다.

위의 두가지 예를 다음과 같은 기호로 쓸수 있습니다.

$S \Rightarrow ^ ab$, $S \Rightarrow ^ aabb$

위 식의 의미는 derivation을 몇번이건 하면 $ab$, $aabb$를 만들수 있다는 것입니다.

Grammer와 language와의 관계 첫번째는 Grammer가 주어졌을때 만들수 있는 sentence로 생각할수 있습니다. $$L(G)=\{w \in T^* ; S \Rightarrow^* w\}$$ 위 식의 의미는 start variable $S$에서 derivation 해서 나올수 있는 모든 가능한 sentence를 의미합니다. 또한 반대로 language가 주어졌을때 해당 language를 만들기 위해 어떠한 grammer를 적용할지 생각해 볼수 있습니다. 예를 들어 $L = \{a^n b^{n+1} ; n \geq 0\}$ 라고 하면 production rule은 다음과 같이 쓸수 있다. $$S \Rightarrow Ab$$ $$A \Rightarrow aAb$$ $$A \Rightarrow \lambda$$ 심화 문제

다음과 production rule이 있다고 합시다.

$$S \Rightarrow SS$$ $$S \Rightarrow \lambda$$ $$S \Rightarrow aSb$$ $$S \Rightarrow bSa$$

위의 방법을 이용하여 만들어진 모든 sentence의 $a$의 갯수 $n_a(w)$ 와 $b$의 갯수 $n_b(w)$ 가 같다는 것은 쉽게 알수 있을것입니다.

하지만 역으로 생각해서 $n_a(w)$ = $n_b(w)$ 인 sentence를 만드는 production rule이 위와 같다는 것은 쉽게 와닿지는 않을 것입니다.

따라서 이것은 귀납적 방법으로 증명을 해보겠습니다.

$n_a(w)$ = $n_b(w)$ 인 sentence의 경우수는 다음과 같이 4가지가 있을수 있습니다.

1. $a \ldots b$

2. $b \ldots a$

3. $a \ldots a$

4. $b \ldots b$

귀납적 방법의 induction 가정으로 $\mid w \mid \leq 2n$ 길이의 sentence에 대해서는 production rule이 성립한다고 가정한다고 하면, sentence 길이가 $\mid w \mid =2n+2$ 인 것에서도 production rule이 성립된다는 것을 보이면 될것입니다. 위 4개의 sentence의 길이가 $2n+2$라고 하고, production rule이 성립이 된다는 것을 보이면 될것입니다.

1, 2번의 sentence는 쉽게 증명할수 있습니다.

1번의 양끝의 a,b를 제외하면 sentence길이는 $2n$이 되고, 2번의 양끝의 b,a를 제외하면 sentence길이는 $2n$이 될것입니다. 가정에서 $2n$에 대해서는 production rule이 성립된다고 하였으므로 1번은 $S \Rightarrow aSb$ derivation으로 성립됨을 알수 있고, 2번은 $S \Rightarrow bSa$ derivation으로 성립됨을 알수 있습니다.

3, 4번의 경우에는

sentence의 어느 중간 시점($t$)을 기준으로 왼쪽의 sentence를 편의상 $w_{left}$ 오른쪽의 sentence를 편의상 $w_{right}$ 라고 한다면 $n_a(w_{left})$ = $n_b(w_{left})$, $n_a(w_{right})$ = $n_b(w_{right})$를 만족하는 중간 지점 $t$는 존재하게 됩니다.

그러면 $S \Rightarrow SS$ derivation을 적용하면 증명할수 있습니다.