계산이론은 컴퓨터가 어떤 입력을 받아 어떤 규칙으로 처리할 수 있는지를 수학적으로 다루는 분야이다. 가장 먼저 필요한 것은 입력을 구성하는 기호와 기호의 나열을 엄밀하게 정의하는 일이다. 프로그램 소스 코드, 네트워크 메시지, 숫자의 표현도 결국 유한한 기호의 나열로 볼 수 있다.
Alphabet
Alphabet은 기호의 유한하고 공집합이 아닌 집합이다. 보통 로 나타낸다.
위 Alphabet은 두 Symbol , 을 가진다. 영어 소문자를 사용하는 경우에는 다음과 같이 둘 수도 있다.
Alphabet 자체는 문자열이 아니라 문자열을 만드는 재료의 집합이다. 각 원소는 더 작은 단위로 분석하지 않는 하나의 Symbol로 취급한다.
String
String은 Alphabet의 Symbol을 유한한 순서로 나열한 것이다. 은 위의 String이다.
String의 길이는 포함된 Symbol의 개수이며 로 나타낸다.
같은 Symbol이 여러 번 등장하면 등장한 횟수만큼 길이에 포함된다. String의 순서도 중요하므로 과 은 서로 다른 String이다.
Empty String
Symbol을 하나도 포함하지 않는 String을 Empty String이라고 하며 로 나타낸다.
Empty String은 String이므로 Language의 원소가 될 수 있다. 그러나 아무 원소도 없는 Empty Set과는 다르다.
은 원소가 0개인 집합이고, 은 Empty String 하나를 원소로 가지는 집합이다.
Concatenation
두 String을 순서대로 이어 붙이는 연산을 Concatenation이라고 한다. , 이면
이다. 일반적으로 Concatenation은 교환법칙을 만족하지 않는다.
Empty String은 Concatenation의 항등원이다.
길이는 더해진다.
String의 거듭제곱
String 를 반복하여 연결한 것을 으로 나타낸다.
예를 들어 이면
이다.
Prefix, Suffix와 Substring
String 가 로 표현될 때 는 Prefix, 는 Suffix, 는 Substring이라고 할 수 있다.
예를 들어 에서
- 는 Prefix이다.
- 는 Suffix이다.
- 는 Substring이다.
- 는 문자가 연속하지 않으므로 Substring이 아니다.
자기 자신과 Empty String도 Prefix와 Suffix로 허용하는 정의가 일반적이다. 자기 자신을 제외한 Prefix는 Proper Prefix라고 한다.
혼동하기 쉬운 점
- Alphabet은 Symbol의 집합이고 String은 Symbol의 순서 있는 나열이다.
- 은 길이가 0인 String이고 은 원소가 없는 Set이다.
- 은 Alphabet일 수 있지만 은 그 Alphabet 위의 String이다.
- Concatenation은 보통 교환법칙이 성립하지 않는다.
정리
- Alphabet은 유한하고 공집합이 아닌 Symbol의 집합이다.
- String은 Alphabet의 Symbol을 유한하게 나열한 것이다.
- Empty String의 길이는 0이다.
- Concatenation은 String을 순서대로 이어 붙이는 연산이다.
- Prefix, Suffix, Substring은 String 내부의 위치 관계를 나타낸다.
연습 문제
1번
일 때 다음 중 에 속하는 것을 모두 고른다.
2번
, 일 때 , , , 를 구한다.
풀이
1번
, , 는 모두 , 만 사용하거나 아무 Symbol도 사용하지 않았으므로 에 속한다. 에는 Alphabet에 없는 가 포함되므로 속하지 않는다.
2번
길이는 Concatenation 전 길이의 합이므로
이다.