Introduction
'학문'이란 어떤 '문제'를 푸는 과정으로 일축할 수 있다. 예를 들어, 건축공학은 집을 잘 짓는데 필요한 '문제'를 해결해 나가는 학문이고, 물리학이란 여러 가지 자연 현상들을 설명하고 예측하는 '문제'를 해결해 나가는 학문이다.
그렇다면 컴퓨터 과학(Computer Science)는 어떤 학문일까? 여러가지 정의가 있겠지만, 필자는 '문제를 푸는 방법', 그 자체에 대한 학문이라고 생각한다. 그 문제를 풀기 위해 우리는 컴퓨터라는 계산 기계를 이용하기 때문에 우리는 이 학문을 컴퓨터 과학이라고 부른다.
앞으로 연재해 나갈 포스트들은 컴퓨터로 어떠한 문제를 풀 수 있는지(Computability), 그러한 문제들이 얼마나 풀기 어려운지(Intractability)에 대해 다룰 것이다.
Language
먼저 알파벳과 스트링에 대한 것들을 정의하자.
정의 0.1
- 알파벳(alphabet)이란 글자들의 유한 집합을 의미한다. 주로 $\Sigma$로 표현한다. 예를 들어, $\{a, b, c\}$, $\{0, 1\}$ 등은 모두 알파벳이다. 별 다른 설명이 없다면 알파벳은 0과 1을 사용한다.
- 스트링(string)이란 유한 개의 알파벳을 나열한 것이다. 주로 $w$로 표현한다. 예를 들어, 010, abaab 등은 스트링이다.
- 스트링의 길이(length)는 스트링 내의 알파벳의 개수를 의미하고 주로 $\vert w \vert$로 나타낸다. 예를 들어, 010은 길이가 3인 스트링이다. 길이가 0인 스트링은 $\epsilon$으로 표기한다.
- $\epsilon$을 포함하여 알파벳 $\Sigma$ 상의 모든 스트링의 집합을 $\Sigma^*$로 표현한다. 예를 들어 $\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, \cdots\}$을 의미한다.
- 두 스트링의 접합(concatenation) $xy$는 $x$ 뒤에 $y$를 붙인 것이다. 예를 들어, $x = 0, y= 11$이면 $xy = 011$이다.
- 스트링의 역(Reverse) $w^R$는 알파벳을 역순으로 나열한 것이다. 예를 들어, $w = 011$이면 $w^R = 110$이다.
우리는 $\Sigma^*$의 부분집합을 언어(language)라고 하자. 주로 $L$로 표기한다. 언어의 연산은 다음과 같은 것들이 있다.
- 언어 $L_1, L_2$의 접합(concatenation)은 다음과 같다. $$\{uv \;\vert\; u \in L_1, v \in L_2 \}$$ 또한 $L^k = L^{k-1} L (k>1)$로 정의된다.
- $L^*$는 다음과 같이 정의된다. $$L^* = L^0 \cup L^1 \cup L^2 \cup \cdots $$
우리가 앞으로 다룰 문제(problem)는 어떤 스트링 $w$가 어떤 언어 $L$에 속하는지 아닌지를 알고 싶은 것이다.
예제 0.1
스트링 $w = 101$이 $L = \{ w \;\vert\; w = w^R \}$에 속하는지 결정하라.
예제 0.2
언어의 개수는 몇 개인가? 자연수 집합의 크기인가 실수 집합의 크기인가?