Languages

상위 문서: Sets

개요

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

Alphabets and Strings

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

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

String Notation

문자열 $w$의 $i$번째 기호는 $w(i)$와 같이 나타낸다.

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

Cardinality of ${\mathrm{\Sigma }}^{*}$

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

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

Languages

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

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

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

The Set of All Languages

모든 언어들의 집합은 ${𝒫}({\mathrm{\Sigma }}^{*})$과 같이 나타낸다. 즉 ${\mathrm{\Sigma }}^{*}$의 멱집합이다. 이때 ${𝒫}({\mathrm{\Sigma }}^{*})$은 비가산이다. 이는 아래와 같이 증명된다.

• |${\mathrm{\Sigma }}^{*}$|는 가산 무한 집합이다.
• 하지만 어떤 집합에 대해서도 |$A$| $<$ |${𝒫}(A)$|이다.
• 따라서 |${\mathrm{\Sigma }}^{*}$| $<$ |${𝒫}({\mathrm{\Sigma }}^{*})$|이다.