Languages - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:22:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:22 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Sets#Languages\|Sets]]		상위 문서: [[Sets#Languages\|Sets]]

Pinkgo: /* The Set of All Languages */

2025-09-10T05:11:09Z

The Set of All Languages

← 이전 판		2025년 9월 10일 (수) 05:11 판
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>\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>\|이다.

	==각주==		==각주==

Pinkgo: /* The Set of All Languages */

2025-09-10T05:10:54Z

The Set of All Languages

← 이전 판		2025년 9월 10일 (수) 05:10 판
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>\|이다.

	==각주==		==각주==

Pinkgo: /* The Set of All Languages */

2025-09-10T05:10:36Z

The Set of All Languages

← 이전 판		2025년 9월 10일 (수) 05:10 판
33번째 줄:		33번째 줄:
	모든 언어들의 집합은 <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>\|이다.


	==각주==		==각주==

Pinkgo: /* The Set of All Languages */

2025-09-10T05:10:25Z

The Set of All Languages

← 이전 판		2025년 9월 10일 (수) 05:10 판
33번째 줄:		33번째 줄:
	모든 언어들의 집합은 <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:09에 Pinkgo님의 편집

2025-09-10T05:09:59Z

← 이전 판		2025년 9월 10일 (수) 05:09 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
			언어(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>\|이다.


	==각주==		==각주==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Sets ==개요== ==각주==

2025-09-10T04:38:30Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Sets ==개요== ==각주==

새 문서

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

==개요==

==각주==

← 이전 판		2025년 9월 10일 (수) 05:10 판
33번째 줄:		33번째 줄:
	모든 언어들의 집합은 <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 판
33번째 줄:		33번째 줄:
	모든 언어들의 집합은 <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>\|이다.


	==각주==		==각주==