Languages

상위 문서: Sets

개요

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

Alphabets and Strings

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

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

String Notation

문자열 [math]\displaystyle{ w }[/math]의 [math]\displaystyle{ i }[/math]번째 기호는 [math]\displaystyle{ w(i) }[/math]와 같이 나타낸다.

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

Cardinality of [math]\displaystyle{ \Sigma^* }[/math]

알파벳 [math]\displaystyle{ \Sigma }[/math]가 유한하고 공집합이 아니면 [math]\displaystyle{ \Sigma^* }[/math]은 가산 무한이라는 정리(theorem)이 존재한다. 이는 아래와 같은 증명을 따른다.

• 사전식 순서(lexicographic order)로 문자열을 나열할 수 있다.
• 예: [math]\displaystyle{ \{a,b\} }[/math]일 경우, [math]\displaystyle{ \epsilon, a, b, aa, ab, ba, bb, aaa, aab, ... }[/math]
• 따라서 [math]\displaystyle{ \Sigma^* }[/math]는 자연수와 일대일 대응이 가능하므로 가산 무한이다.

Languages

언어(Languages)란 문자열 [math]\displaystyle{ \Sigma^* }[/math]의 부분집합임을 의미한다. 즉, 문자열들의 집합이 언어이다. 예를 들면:

• [math]\displaystyle{ \empty }[/math]: 공언어
• [math]\displaystyle{ \Sigma^* }[/math]: 모든 문자열을 포함하는 언어
• [math]\displaystyle{ {w} }[/math]: 문자열 [math]\displaystyle{ w }[/math]만 포함하는 싱글톤 언어이다.
• [math]\displaystyle{ \Sigma }[/math]: 알파벳의 모든 단일 문자 문자열의 집합을 의미한다.

이때 언어들은 집합이므로, 합집합, 교집합, 여집합 등을 정의할 수 있다.

The Set of All Languages

모든 언어들의 집합은 [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math]과 같이 나타낸다. 즉 [math]\displaystyle{ \Sigma^* }[/math]의 멱집합이다. 이때 [math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math]은 비가산이다. 이는 아래와 같이 증명된다.

• |[math]\displaystyle{ \Sigma^* }[/math]|는 가산 무한 집합이다.
• 하지만 어떤 집합에 대해서도 |[math]\displaystyle{ A }[/math]| [math]\displaystyle{ \lt }[/math] |[math]\displaystyle{ \mathcal{P}(A) }[/math]|이다.
• 따라서 |[math]\displaystyle{ \Sigma^* }[/math]| [math]\displaystyle{ \lt }[/math] |[math]\displaystyle{ \mathcal{P}(\Sigma^*) }[/math]|이다.