다른 명령
| 32번째 줄: | 32번째 줄: | ||
===The Set of All Languages=== | ===The Set of All Languages=== | ||
모든 언어들의 집합은 <math>\mathcal{P}(\Sigma^*)</math>과 같이 나타낸다. 즉 <math>\Sigma^*</math>의 멱집합이다. 이때 <math>\mathcal{P}(\Sigma^*)</math>은 비가산이다. 이는 아래와 같이 증명된다. | 모든 언어들의 집합은 <math>\mathcal{P}(\Sigma^*)</math>과 같이 나타낸다. 즉 <math>\Sigma^*</math>의 멱집합이다. 이때 <math>\mathcal{P}(\Sigma^*)</math>은 비가산이다. 이는 아래와 같이 증명된다. | ||
* |math>\mathcal{P}(\Sigma^*)</math>|는 가산 무한 집합이다. | * |<math>\mathcal{P}(\Sigma^*)</math>|는 가산 무한 집합이다. | ||
* 하지만 어떤 집합에 대해서도 |<math>A</math>| <math> < </math> |<math>\mathcal{P}(A)</math>|이다. | * 하지만 어떤 집합에 대해서도 |<math>A</math>| <math> < </math> |<math>\mathcal{P}(A)</math>|이다. | ||
* 따라서 |<math>\Sigma^*</math>| <math> < </math> |<math>\mathcal{P}(\Sigma^*)</math>|이다. | * 따라서 |<math>\Sigma^*</math>| <math> < </math> |<math>\mathcal{P}(\Sigma^*)</math>|이다. | ||
==각주== | ==각주== | ||
2025년 9월 10일 (수) 05:10 판
상위 문서: 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{ \mathcal{P}(\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]|이다.