Languages 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Sets#Languages|Sets]]

==개요==
언어(language)란, 특정한 알파벳 위에서 정의된 문자열들의 집합을 말한다. 즉, 언어는 단순한 기호의 나열이 아니라, 수학적으로는 집합이라는 기본적인 수학적 객체(Mathematical Object)로 이해할 수 있다. 해당 문서에서는 언어에 대한 집합론적인 관점을 다룬다.

==Alphabets and Strings==
알파벳(Alphabets)이란 기호(symbol)들의 유한하고 공집합이 아닌 집합을 의미한다. 예를 들면, <math>\Sigma = \{a,b\}, \{0,1\}, \{A,B,C,...,Z\}</math>이 있다. 

문자열(String)이란 알파벳 <math>\Sigma</math> 위의 유한한 기호들의 나열을 의미한다. 문자열 <math>w = w_1w_2\cdots w_n</math>이 그 예시이다. 또한 어떤 문자열 <math>w</math>의 길이가 n이라는 것은 <math>n = </math>|<math>w</math>|과 같이 표시한다. 길이가 0인 문자열은 빈 문자열(empty string)이라고 하고 기호로는 <math>\epsilon</math>과 같이 나타낸다. 또한 <math>\Sigma^*</math>는 알파벳 <math>\Sigma</math>로 만들 수 있는 모든 문자열들의 집합을 의미한다.

===String Notation===
문자열 <math>w</math>의 <math>i</math>번째 기호는 <math>w(i)</math>와 같이 나타낸다. 

두 문자열 <math>u, v</math>의 연결(concatenation)은 <math>uv</math>와 같이 표시하며, 해당 문자열의 길이는 두 문자열의 길이의 합이다. 문자열을 결합할 때에는 결합법칙(Associativity)이 존재하며, 이는 <math>(uv)w = u(vw)</math>와 같다. 또한 항등원(identity)이 존재한다. 만약 <math>\epsilon</math>이 항등원이라면, <math>u\epsilon = \epsilon u = u</math>가 성립한다.

===Cardinality of <math>\Sigma^*</math>===
알파벳 <math>\Sigma</math>가 유한하고 공집합이 아니면 <math>\Sigma^*</math>은 가산 무한이라는 정리(theorem)이 존재한다. 이는 아래와 같은 증명을 따른다.
* 사전식 순서(lexicographic order)로 문자열을 나열할 수 있다.
* 예: <math>\{a,b\}</math>일 경우, <math>\epsilon, a, b, aa, ab, ba, bb, aaa, aab, ...</math>
* 따라서 <math>\Sigma^*</math>는 자연수와 일대일 대응이 가능하므로 가산 무한이다.

==Languages==
언어(Languages)란 문자열 <math>\Sigma^*</math>의 부분집합임을 의미한다. 즉, 문자열들의 집합이 언어이다. 예를 들면:
* <math>\empty</math>: 공언어
* <math>\Sigma^*</math>: 모든 문자열을 포함하는 언어
* <math>{w}</math>: 문자열 <math>w</math>만 포함하는 싱글톤 언어이다.
* <math>\Sigma</math>: 알파벳의 모든 단일 문자 문자열의 집합을 의미한다.
이때 언어들은 집합이므로, 합집합, 교집합, 여집합 등을 정의할 수 있다.

===The Set of All Languages===
모든 언어들의 집합은 <math>\mathcal{P}(\Sigma^*)</math>과 같이 나타낸다. 즉 <math>\Sigma^*</math>의 멱집합이다. 이때 <math>\mathcal{P}(\Sigma^*)</math>은 비가산이다. 이는 아래와 같이 증명된다.
* |math>\mathcal{P}(\Sigma^*)</math>|는 가산 무한 집합이다.
* 하지만 어떤 집합에 대해서도 |<math>A</math>| <math> < </math> |<math>\mathcal{P}(A)</math>|이다.
* 따라서 |<math>\Sigma^*</math>| <math> < </math> |<math>\mathcal{P}(\Sigma^*)</math>|이다.

==각주==