형식언어 계층과 오토마타

(Formal Language Hierarchy and Automata)

형식 언어와 오토마타 : Peter Linz 저서, 장직현. 김응모. 엄영익. 한광록 공역, 사이텍미디어, 2001 (원서 : An Introduction to Formal Languages and Automata. 3rd ed, Jones and Bartlett. 2001), Page 289~312

1. 순환적 언어와 순환적으로 열거가능한 언어

     (1) 순환적으로 열거가능하지 않은 언어들

     (2) 순환적으로 열거가능하지 않은 언어

     (3) 순환적으로 열거가능하지만 순환적이지 않은 언어

2. 무제한 문법

     연습문제

3. 문맥-인식 문법과 언어

     (1) 문맥-인식 언어와 선형 한정 오토마타

     (2) 순환적인 언어와 문맥-인식 언어들 사이의 관계

     연습문제

4. Chomsky 계층

     연습문제

형식 언어에 대한 연구로 우리의 관심을 다시 돌려보자. 우리의 직접적인 목표는 튜링 기계들과 그들에 대한 몇몇 제약들과 연관된 언어들을 검사하는 것이다. 튜링 기계는 여러 가지 형태의 알고리즘적인 계산들을 수행할 수 잇기 때문에 튜링 기계와 연관된 언어군은 매우 광범위하다는 것을 알게 될 것이다. 여기에는 정규 언어와 문맥-자유 언어뿐만 아니라 그 밖의 범위에 놓여 있는 여러 가지 예들이 포함된다. 특별한 문제는 어떤 튜링 기계에 의해서도 인식되지 않는 언어가 존재하는지에 관한 사항이다. 우리는 우선 튜링 기계들보다 더 많은 수의 언어들이 존재한다는 것을 보이고 따라서 대응하는 어떤 튜링 기계도 존재하지 않는 언어가 존재하여야 한다는 것을 보임으로써 이 문제에 대한 답을 할 것이다. 그 증명은 간단하고 정연하지만, 구성적이 아니고 문제를 간파하기 거의 어렵다. 때문에 보다 명료한 예를 통하여 튜링 기계에 의하여 인식될 수 없는 언어의 존재를 확립할 것이다. 이 예는 실제로 우리들로 하여금 그와 같은 언어를 확인할 수 있도록 해준다. 다른 관찰 방향은 튜링 기계와 어떤 형식의 문법들 사이에 관계를 살펴보고 이들 문법들과 정규 문법 또는 문맥-자유 문법과의 연관성을 확립하는 것이다. 이들 관계는 문법의 계층을 이끌어 내고 그 계층을 통하여 언어군들을 분류해 내는 방법을 찾아낸다. 몇 가지 집합 이론의 다이어그램으로 여러 가지 언어군들 사이의 관계를 명확히 나타낼 수 있다.

엄밀히 말하면, 이 장에서의 많은 논의들은 단지 빈 문자열을 포함하지 않는 언어들에 대해서만 유효하다. 이와 같은 제한은 튜링 기계가, 우리가 정의한 바와 같이, 빈 문자열을 승인할 수 없다는 사실에 기인된다. 튜링 기계의 정의를 변경하거나 반복적인 부정을 추가해야만 하는 번거로움을 피하기 위하여, 이 장에서 논의되는 언어들은 다른 특별한 언급이 없다면 λ 를 포함하지 않는 것을 묵시적으로 가정한다. λ 를 포함시켜서 모든 것을 다시 언급하는 것은 어려운 일은 아니지만 이 부분은 독자들에게 맡겨둔다.

1. 순환적 언어와 순환적으로 열거가능한 언어

우리는 먼저 튜링 기계와 연관된 언어들에 대한 용어들을 살펴보기로 한다. 그런 용어들을 살펴보는 데 있어, 승인하는 튜링 기계가 존재하는 언어와 소속성 알고리즘이 존재하는 언어들 사이의 중요한 구별을 해야 한다. 튜링 기계는 이 기계가 승인하지 못하는 입력에 대하여 항상 정지하는 것이 아니기 때문에, 튜링 기계가 승인하는 언어가 소속성 알고리즘이 존재하는 언어라고는 말할 수 없다.

 정의 1

언어 L 을 승인하는 튜링 기계가 존재한다면 그 언어는 순환적으로 열거가능하다 (recursively enumerable) 고 한다.

이 정의는 다음과 같은 성질을 만족하는 튜링 기계 M 이 존재한다는 것을 의미한다. 모든 w ∈ L 에 대하여,

여기서 는 종료 상태이다. 이 정의는 L 에 속하지 않는 w 에는 어떤 일이 발생하는지에 대해서는 아무 것도 언급하지 않고 있다 ; 기계는 비종료 상태에서 정지하거나 결코 정지하지 않고 무한 루프에 들어갈 것이다. 우리는 더 욕심을 내어 기계가 모든 주어진 입력이 그 언어에 속하는지 아닌지를 알려주기를 요구할 수 있다.

 정의 2

L 을 알파벳 Σ 에 대한 언어라 하자. 만일 언어 L 을 인식하고, 또한 Σ⁺ 에 속하는 모든 w 에 대하여 정지하는 튜링 기계가 존재한다면, 이 언어 L 은 순환적 (recursive) 이라고 한다.

만일 언어 L 이 순환적이라면, 열거 절차가 쉽게 구성될 수 있다. M 이 순환적 언어 L 에 대한 소속성을 결정하는 튜링 기계라고 하자. 먼저 고유 순서 (proper order) 로 Σ⁺ 에 속하는 모든 문자열 을 생성하는 다른 튜링 기계 을 구성한다. 이들 문자열들이 생성될 때 이들은 M 의 입력이 된다. M 은 입력으로 주어진 문자열들이 L 에 속할 때만 테이프에 쓰여지도록 수정된 것이다.

모든 순환적으로 열거가능한 언어에 대하여 열거 절차가 존재한다는 것을 확인하는 것은 그렇게 쉬운 일이 아니다. 앞의 논의를 그대로 이용할 수 없다. 왜냐하면 어떤 가 L 에 속하지 않는다면 테이프에 를 가지고 시작되는 기계 M 은 결코 정지하지 않을 수도 있고 따라서 열거에 있어 다음에 오는 문자열들을 처리할 수 없을 수도 있게 된다. 이와 같은 일이 발생하지 않도록 하기 위하여, 계산이 다른 방법으로 수행된다. 먼저 으로 하여금 을 생성하게 하고 M 이 에 대해 한 단계 이동을 실행하도록 한다. 그리고 나서 은 를 생성하게 하고 M 이 에 대해 한 단계 이동을 실행하도록 한다. 뒤이어 에 대한 두 번째 이동을 실행하도록 한다. 그 다음에 가 생성되고 에 대한 한 단계가 실행된다. 에 대해서는 두 번째 단계, 에 대해서는 세 번째 단계 등을 실행하도록 한다. 실행 순서는 그림 1 과 같이 묘사된다. 이와 같은 방법에 의하면, M 은 결코 무한 루프에 빠지지 않게 된다. 모든 w ∈ L 가 에 의하여 생성되고 유한 단계 내에 M 에 의하여 승인되기 때문에, L 에 속하는 모든 문자열은 결국은 M 에 의하여 생성되게 된다.

그림 1

열거 절차가 존재하는 모든 언어는 순환적으로 열거가능하다는 것을 쉽게 알 수 있다. 우리는 주어진 입력 문자열을 단순히 열거 절차에 의하여 연속적으로 생성된 문자열들과 단순히 비교하면 된다. w ∈ L 이라면 결국은 일치되는 것을 만나게 되고 처리 과정은 종료될 수 있다.

정의 1 과 정의 2 는 순환적이거나 순환적으로 열거가능한 언어의 본질에 대한 통찰력을 거의 제시하지 못하고 있다. 이 정의들은 튜링 기계와 연관된 언어군들에 이름을 붙이지만 이들 언어군에 속한 대표적인 언어들의 본질을 밝히지는 못하고 있다. 이 정의들은 이들 언어들 사이의 관계나 앞에서 다루었던 언어군들과의 연결성에 대하여 알려주는 바가 별로 없다. 그래서 "순환적으로 열거가능하지만 순환적이 아닌 언어들이 있는가?" 그리고 "어떤 방식으로든 기술할 수 있는 언어들 가운데 순환적으로 열거가능하지 않은 언어들이 있는가?" 등과 같은 여러 가지 질문에 직면하게 된다. 몇 가지 답변을 할 수 있겠지만 그와 같은 질문들, 특히 두 번째 질문을 설명할 아주 명백한 예를 생성할 수는 없을 것이다.

(1) 순환적으로 열거가능하지 않은 언어들

우리는 다양한 방법으로 순환적으로 열거가능하지 않은 언어의 존재를 보일 수 있다. 이 가운데 하나는 매우 간단하고 아주 기초적이고 정교한 수학의 결과를 이용한다.

 정리 1

S 를 무한 가산 집합이라 하자. 그러면 S 의 멱집합 는 가산 집합이 아니다.

증명 : 라 하자. 의 임의의 원소 t 는 0 과 1 의 순서열로 표현될 수 있다. 가 t 에 속하고 오직 그럴 때에만 순서열은 i 번째 위치에 1 을 갖는다. 예를 들면, 집합 는 10101... 로 표현되는 반면에 집합 은 01100100 ... 로 표현된다. 명백하게 를 가산 집합이라고 가정하자. 그러면 이 집합의 원소들은 어떤 순서로, 말하자면 와 같은 순서로, 쓰여질 수 있다. 이들을 그림 2 와 같이 테이블에 집어넣을 수 있다. 이 테이블에서 주 대각선에 있는 원소들을 선택하고 각 원소의 보수 (complement) 를 취한다. 즉, 0 은 1 로 1 은 0 으로 치환한다. 그림 2 의 예에서 원소들은 1100... 이고, 따라서 0011... 을 결괄 얻는다. 이 새로운 순서열은 의 어떤 원소를 나타낸다. 어떤 i 에 대하여 라 하자. 그러나 이것은 은 될 수 없다. 이와 같은 모순은 가 가산 집합이라는 가정을 포기해야만 해결될 수 있는 논리적인 난국을 만들어 낸다.

그림 2

이와 같은 논의를, 테이블의 대각선 원소들에 대한 조작을 포함하기 때문에, 대각선화 (diagonalization) 라고 한다. 이와 같은 기법은 실수의 집합이 가산 집합이 아니라는 것을 증명하기 위하여 이 방법을 사용한 수학자 G. F. Cantor 의 공적에서 비롯하였다. 앞으로, 여러 곳에서 유사한 논의를 하게 될 것이다. 정리 1 은 가장 순수한 형태의 대각선화이다.

이 결과의 즉각적인 결론으로서, 어떤 면에서, 언어들보다 더 적은 수의 튜링 기계가 존재한다는 것을 보일 수 있고, 따라서 순환적으로 열거할 수 없는 언어가 존재하여야 한다.

 정리 2

임의의 알파벳 Σ 에 대하여, 순환적으로 열거가능하지 않은 언어가 존재한다.

증명 : 언어는 Σ^* 의 부분집합이고, 그와 같은 부분집합은 언어이다. 그러므로 모든 언어들의 부분집합은 정확히 이다. Σ^* 는 무한 집합이기 때문에 정리 1 로부터 Σ 에 대한 모든 언어들의 집합은 가산 집합이 아니다. 그러나 모든 튜링 기계의 집합은 열거될 수 있다. 따라서 모든 순환적으로 열거가능한 언어들의 집합은 가산 집합이다. 이 절의 끝에 있는 연습문제 16 에 의하여, 이는 순환적으로 열거가능하지 않는 어떤 언어들이 반드시 존재해야 한다는 것을 의미한다.

이 증명은 간단 명료하지만 여러 가지 점에서 불만족스러운 점이 있다. 아주 비구성적이고 순환적으로 열거가능하지 않은 언어들의 존재를 알려주고 있는 반면에 이런 언어들이 어떻게 생겼는지에 대한 느낌을 전혀 주지 못하고 있다. 다음 결과들을 통해서, 보다 명료하게 결론을 조사해 보기로 한다.

(2) 순환적으로 열거가능하지 않은 언어

직접적인 알고리즘 형태로 기술될 수 있는 모든 언어가 튜링 기계에 의하여 승인될 수 있고 또한 순환적으로 열거가능하기 때문에, 순환적으로 열거가능하지 않은 언어에 대한 기술은 간접적이어야 한다. 그럼에도 불구하고 이것은 가능하다. 이 논의에는 대각선화 주제에 대한 변형이 포함된다.

 정리 3

여집합이 순환적으로 열거가능하지 않은 순환적으로 열거가능한 언어가 존재한다.

증명 : Σ = {a} 라 하고, 이와 같은 입력 알파벳을 갖는 모든 튜링 기계의 집합을 생각해 보자. 정리 10.3 에 의하여 이 집합은 가산 집합이고, 따라서 원소들을 등과 같이 순서를 매길 수 있다. 각 튜링 기계 에 대하여 연관되는 순환적으로 열거가능한 언어 가 존재한다. 반대로, Σ 로 구성된 각각의 순환적으로 열거가능한 언어에 대하여, 그 언어를 승인하는 튜링 기계가 존재한다.

여기서 다음과 같이 정의된 새로운 언어 L 을 생각해 보자. i ≥ 1 인 모든 i 에 대하여 이고 오직 그럴 때에만 는 L 에 속한다. 는 그리고 도, 반드시 참이 되거나 거짓이 되어야 하기 때문에, 언어 L 이 잘 정의되었다는 것은 분명하다. 다음과 같이 L 의 여집합을 생각해 보자.

                                                                       (1)

이 언어는 잘 정의되어 있지만, 앞으로 보이는 바와 같이, 순환적으로 열거가능하지 않다.

이것을 모순에 의한 증명으로 보일 것이다. 시작에 이 언어가 순환적으로 열거가능하다고 가정한다. 만일 그렇다면 다음 식을 만족하는 어떤 튜링 기계 가 존재해야만 한다.

                                                                                   (2)

문자열 를 생각해 보자. 이 문자열은 L 에 속하는지 에 속하는가? 이라 한다면 식 (2) 에 의하여

를 의미한다. 그러나 지금 식 (1) 은

를 의미한다. 반대로, 가 L 에 속한다고 가정하면, 이고 식 (2) 는

를 의미한다. 그러나 지금 식 (1) 에 의하여

가 된다. 이와 같은 모순은 불가피하고, 따라서 가 순환적으로 열거가능하다는 가정이 거짓이라는 결론에 도달하게 된다.

언급한 바와 같이 정리의 증명을 끝내기 위하여, L 이 순환적으로 열거가능하다는 것을 보여야 한다. 이를 위하여 잘 알려진 튜링 기계들에 대한 열거 절차를 이용할 수 있다. 가 주어진다면, 먼저 a 의 개수를 세어서 i 를 찾는다. 그리고 나서 를 찾기 위하여 튜링 기계들에 대한 열거 절차를 이용한다. 마지막으로 이 기계에 대한 기술이 와 함께 에 대한 의 동작을 시뮬레이션하는 범용 튜링 기계 에게 주어진다. 만일 가 L 에 속한다면, 에 의하여 수행되는 계산은 결국은 정지하게 될 것이다. 이와 같이 결합된 결과는 모든 를 승인하는 튜링 기계가 된다. 그러므로 정의 1 에 의하여 L 은 순환적으로 열거가능하다.

식 (1) 을 통하여, 이 정리의 증명은 순환적으로 열거가능하지 않은 잘 정의된 언어를 명백하게 나타내었다. 이것은 에 대한 쉽고 직관적인 해석이 존재한다고 말하는 것은 아니다. 이 언어에 속한 몇 개의 문자열들을 보이는 것보다 그 이상을 보이는 것은 어려운 일이 될 것이다. 그럼에도 불구하고 은 적절하게 정의된다.

(3) 순환적으로 열거가능하지만 순환적이지 않은 언어

다음으로 순환적으로 열거가능하지만 순환적이지 않은 언어에 대하여 설명한다. 다시금, 우리는 다소 초보적인 방법으로 이를 보일 필요가 있다. 보조적인 결과를 확립하는 것으로 이 문제를 시작하기로 한다.

 정리 4

만일 언어 L 과 이 언어의 여집합인 언어 모두가 순환적으로 열거가능하다면, 두 언어 모두 순환적이다. 만일 언어 L 이 순환적이면, 도 순환적이고, 결과적으로 두 언어 모두 순환적으로 열거가능하다.

증명 : 만일 L 과 모두가 순환적으로 열거가능하다면 언어 L 과 에 대한 열거 절차로 작용하는 튜링 기계 M 과 이 각각 존재한다. M 은 L 에 속하는 등을 생성할 것이고, 는 에 속하는 등을 생성할 것이다. 여기서 임의의 가 주어졌다고 가정하자. 먼저 M 이 을 생성하게 하고 과 w 를 비교한다. 만일 이들이 같지 않다면 이 을 생성하게 하고 다시 비교한다. 계속할 필요가 있다면, M 은 를 생성하고 이 를 생성하는 과정을 계속 진행한다. 어떤 든지 M 이나 에 의해서 생성될 것이며, 결국은 비교가 일치하는 결과를 얻게 될 것이다. 만일 일치된 문자열이 M 에 의하여 생성된다면 w 는 L 에 속하게 되고 그렇지 않다면 에 속하게 된다. 이 절차는 L 과 모두에 대한 소속성 알고리즘이 되고, 따라서 그 두 언어 모두 순환적이다.

역으로, L 이 순환적이라고 가정하자. 그러면 이 언어에 대한 소속성 알고리즘이 존재한다. 그러나 이 알고리즘은 단순히 그 결과의 반대를 취함으로써 에 대한 소속성 알고리즘이 된다. 그러므로 은 순환적이다. 모든 순환적인 언어가 순환적으로 열거가능하기 때문에 그 증명은 완료된다.

이 정리로부터, 순환적으로 열거가능한 언어군과 순환적인 언어군이 동일하지 않다는 것을 직접적으로 결론을 내릴 수 있다. 정리 3 의 언어 L 은 순환적으로 열거가능한 언어군에 속하지만 순환적 언어군에 속하지는 않는다.

 정리 5

순환적이지 않지만 순환적으로 열거가능한 언어가 존재한다. 즉, 순환적인 언어군은 순환적으로 열거가능한 언어군의 진부분 집합이다.

증명 : 정리 3 의 언어 L 를 생각해 보자. 이 언어는 순환적으로 열거가능하지만 그 여집합은 순환적으로 열거가능하지 않다. 정리 4 에 의하여 이 언어는 순환적이지 않으며, 우리가 찾고 있는 예를 제시해 준다.

따라서 소속성 알고리즘을 구성할 수 없는 아주 잘 정의된 언어들이 존재한다는 결론을 내릴 수 있다.

연습문제

1. 실수의 집합은 가산 집합이 아님을 증명하라.

2. 순환적으로 열거가능하지 않은 모든 언어들의 집합은 가산 집합이 아님을 증명하라.

3. L 을 유한언어라고 하자. 가 순환적으로 열거가능한 언어임을 보여라. 또한 에 대한 열거 절차를 제안하라.

4. L 을 문맥-자유 언어라고 하자. 가 순환적으로 열거가능한 언어임을 보이고 또 에 대한 열거 절차를 제안하라.

5. 만약 어떤 언어가 순환적으로 열거가능하지 않다면 그 여집합이 순환적일 수 없음을 보여라.

6. 순환적으로 열거가능한 언어군이 합집합에 대하여 폐포 성질이 성립함을 보여라.

7. 순환적으로 열거가능한 언어군이 교집합에 대하여 폐포 성질이 성립하는가?

8. 순환적인 언어군이 합집합과 교집합에 대하여 폐포 성질이 성립함을 보여라.

9. 순환적으로 열거가능한 언어군과 순환적인 언어군이 각각 전도 (reversal) 에 대하여 폐포 성질이 성립함을 보여라.

10. 순환적인 언어군은 접합에 대하여 폐포 성질이 성립하는가?

11. 문맥-자유 언어의 여집합이 반드시 순환적인 언어임을 증명하라.

12. 은 순환적이고, 는 순환적으로 열거가능하다고 하자. 이 순환적으로 열거가능함을 보여라.

13. L 을 L 의 원소들을 고유 순서로 열거할 수 있는 튜링 기계가 존재하는 언어라 하자. 이 성질이 L 이 순환적임을 뜻하는 것을 보여라.

14. 만약 L 이 순환적이라면, 역시 순환적이라고 할 수 있는가?

15. 튜링 기계를 위한 특정한 부호화를 선택하고, 그 부호화를 가지고 정리 3 의 언어 의 한 원소를 찾아라.

16. 은 가산 집합이고, 는 가산 집합이 아니며, 라고 하자. 는  에 포함되지 않는 무한 개의 원소들을 가지고 있어야 함을 보여라.

17. 연습문제 16 에서 이 가산 집합이 아님을 보여라.

18. S 가 유한 집합일 경우 정리 1 이 옳지 못한 이유를 보여라.

19. 모든 무리수 (irrational numbers) 들의 집합은 가산 집합이 아님을 보여라.

2. 무제한 문법

순환적으로 열거가능한 언어와 문법과의 관계를 관찰하기 위하여 제 1 장의 문법에 대한 일반적인 정의를 다시 살펴보기로 한다. 정의 1 에서 생성규칙은 아무 형태나 취할 수 있도록 허용되었다. 그리고 나서 특별한 문법 형태를 얻기 위하여 여러 가지 제약들이 가해졌다. 만일 일반적인 형태를 취하고 아무런 제약도 가해지지 않는다면 이 문법을 무제한 문법이라 한다.

 정의 3

모든 생성규칙이 다음과 같은 형태를 하고 있다면 문법 G = (V, T, S, P) 는 무제한 문법 (unrestricted grammar) 이라고 한다.

u → v

여기서 이다.

무제한 문법에서는 본래 생성규칙에 아무런 조건을 부여하지 않는다. 변수나 단말들이 몇 개라도 오른쪽이나 왼쪽에 올 수 있고, 아무 순서로 나타나도 괜찮다. 유일한 제약이 있는데 그것은 생성규칙의 좌변에 λ 는 올 수 없다는 것이다.

우리가 확인하는 바와 같이, 무제한 문법은 지금까지 공부한 정규 문법이나 문맥-자유 문법과 같은 제한적 형태이 문법보다 훨씬 강력한 문법이다. 사실 무제한 문법들은 가장 큰 언어군과 연관된다. 따라서 우리는 기계적인 방법으로 인식하는 것을 기대할 수 있다. 즉, 무제한 문법들은 정확하게 순환적으로 열거가능한 언어군을 생성한다. 두 부분으로 나누어 이것을 보인다. 첫 부분은 아주 간단하지만 두 번째는 장황한 구성을 포함한다.

 정리 6

무제한 문법에 의하여 생성되는 모든 언어는 순환적으로 열거가능하다.

증명 : 문법은 실제로 그 언어에 속한 모든 문자열을 체계적으로 열거하는 프로시저를 정의한다. 예를 들면, 우리는 다음과 같이 한 단계로 유도될 수 있는 L 에 속한 모든 w 를 열거할 수 있다.

S ⇒ w

문법에 대한 생성규칙의 집합은 유한하기 때문에 그와 같은 문자열은 유한 개가 될 것이다. 다음에는 아래와 같이 두 단계로 유도될 수 있는 L 에 속하는 모든 w 를 열거한다.

S ⇒ x ⇒ w

하나의 튜링 기계에 대하여 이와 같은 유도를 시뮬레이션할 수 있고 따라서 그 언어에 대한 열거 프로시저를 얻을 수 있다. 그러므로 이 언어는 순환적으로 열거가능하다.

순환적으로 열거가능한 언어와 무제한 문법들 사이의 관계에서 이 부분은 놀랄 만한 일이 아니다. 문법은 잘 정의된 알고리즘적인 절차에 의하여 문자열을 생성하고 따라서 그 유도는 튜링 기계상에서 수행될 수 있다. 역을 증명하기 위하여, 임의의 튜링 기계가 어떻게 무제한 문법에 의하여 모방될 수 있는지 설명한다.

튜링 기계 M = (Q, Σ, Γ, δ, , ㅁ, F) 가 주어지고 L(G) = L(M) 인 문법 G 를 생성하려고 한다. 이와 같은 구성에 따른 개념은 상대적으로 간단하지만 그 구현은 기호적으로 표시하기가 귀찮다.

튜링 기계의 계산은 (3) 과 같은 일련의 순간 묘사들에 의하여 설명될 수 있기 때문에

                                                                                       (3)

우리는 (3) 이 성립하고 오직 그럴 때에만 이에 대응하는 문법이 (4) 와 같은 성질을 갖도록 준비하려고 할 것이다.

                                                                                     (4)

이와 같은 작업은 그다지 어렵지 않다. 오히려 확인하기 더 어려운 것은 (3) 을 만족하는 모든 문자열 w 에 대하여 실제로 원하는 유도 (즉, S w) 와 (4) 사이를 어떻게 연결시키느냐 하는 문제이다. 이와 같은 목표를 달성하기 위하여 광범위한 개념으로 다음과 같은 성질을 갖는 문법을 구성한다.

1. 모든 w ∈ Σ⁺ 에 대하여 S 는 를 유도할 수 있다.

2. (3) 이 성립하고 오직 그럴 때에만 (4) 가 가능하다.

3. 인 문자열 가 생성될 때 문법은 이 문자열 을 원래의 문자열 w 로 변환한다.

따라서 유도의 완전한 순서 (5) 와 같다.

S w                                                                        (5)

위의 유도에서 세 번째 단계는 까다롭다. 만일 두 번째 단계에서 w 가 변경된다면 문법이 어떻게 w 를 기억할 것인가? 원래의 부호화된 버전이 w 에 대한 두 개의 복사본을 갖도록 문자열을 부호화함으로써 이 문제를 해결한다. 두 번째 것이 (4) 의 단계들에서 사용되는 동안에 첫 번째 것은 저장된다. 종료 상황이 되면 문법은 저장된 w 를 제외한 모든 것을 지워 버린다.

w 에 대한 두 개의 복사본을 만들고 M 의 상태 심볼을 (결국은 문법에 의하여 제거되어야함) 다루기 위하여, 모든 a ∈ Σ ∪ {ㅁ} 와 모든 b ∈ Γ, 그리고 인 모든 i 에 대하여 변수 와 를 도입한다. 변수 는 상태 와 a 와 b 를 부호화하고 변수 는 a 와 b 를 부호화한다.

(5) 에서 첫 번째 단계는 다음과 같은 생성규칙에 의하여 (부호화된 형태로) 성취될 수 있다 : a ∈ Σ 인 모든 a 에 대하여,

S → V_ㅁㅁS|SV_ㅁㅁ|T                                                                         (6)

T →                                                                                    (7)

이들 생성규칙들은 문법으로 하여금 문자열 앞과 뒤에 임의의 개수만큼 공백을 갖는 모든 문자열 의 부호화된 형태를 생성하도록 한다.

두 번째 단계에 대하여 인 튜링 기계 M 의 각 전이에 대하여 (8) 과 같은 생성규칙들을 삽입한다. 모든 a, p ∈ Σ ∪ {ㅁ}, q ∈ Γ 에 대해,

                                                                                    (8)

인 튜링 기계 M 의 각 전이에 대하여 문법 G 에 (9) 와 같은 생성 규칙들을  삽입한다. 모든 a, p ∈ Σ ∪ {ㅁ}, q ∈ Γ 에 대해,

                                                                                   (9)

만일 두 번째 단계에서 M 이 종료 상태에 들어간다면, 문법은 w 를 제외한 모든 것들을 제거하여야 한다. w 는 V 의 첫 번째 첨자에 저장되어 있다. 따라서, 모든 에 대하여, (10) 과 같은 생성규칙들을 포함한다. 모든 a ∈ Σ ∪ {ㅁ}, q ∈ Γ 에 대해,

                                                                                            (10)

이 생성규칙은 문자열의 첫 번째 단말 심볼을 생성하고 그리고 나서 다음의 생성규칙들에 의해 나머지가 다시 작성되도록 한다. 모든 a ∈ Σ ∪ {ㅁ}, q ∈ Γ 에 대해,

                                                                                           (11)

                                                                                           (12)

또한 (13) 과 같은 한 가지 특별한 생성규칙을 필요로 한다.

ㅁ → λ                                                                                             (13)

이 생성규칙은 기계 M 이 입력 w 가 차지하고 있는 테이프의 범위를 벗어나서 이동하는 경우를 처리한다. 이와 같은 경우에 제대로 작업이 되도록 하기 위하여, 먼저 (6) 과 (7) 을 이용하여 사용도니느 테이프의 모든 영역을 나타내는

ㅁ...ㅁㅁ...ㅁ

를 생성한다. 관계없는 공백 심볼들은 마지막에 (13) 형태의 생성규칙에 의하여 제거된다.

다음 예제는 이와 같은 복잡한 구성을 보여주고 있다. 여러 가지 생성규칙들이 어떤 역할을 하고, 왜 필요한지 알아보기 위하여 예제의 각 단계들을 주의깊게 검토해 보도록 한다.

 예제 1

M = (Q, Σ, Γ, δ, , ㅁ, F) 를 다음과 같이 구성된 튜링 기계라 하자 :



Σ = {a, b, ㅁ}

Γ = {ㅁ, ㅠ}



그리고

δ(q₁, ㅁ) = (q₁, ㅁ, R)

δ(q₀, ㅁ) = (q₁, ㅁ, L)

이 기계는 를 인식한다.

(14) 와 같은 계산 과정을 생각해 보자.

q₀aa┣ aq₀a┣ aaq₀ㅁ┣ aq₁aㅁ                                                    (14)

이 계산은 문자열 aa 를 인식한다. 문법 G 를 가지고, 이 문자열을 유도하기 위하여 먼저 (6) 과 (7) 형태의 생성규칙을 사용하여 다음과 같이 적절한 시작 문자열을 얻는다.

S ⇒ SV_ㅁㅁ ⇒ TV_ㅁㅁ ⇒ TV_aaV_ㅁㅁ ⇒ V_a0aV_aaV_ㅁㅁ

마지막 문장 형태는 튜링 기계의 계산을 모방하는 유도 부분에 대한 시작점이다. 이것은 첫 첨자들의 순서열로 원래의 입력 aaㅁ 나머지 첨자들로 초기의 순간적 묘사인 q₀aa 를 포함한다. 다음으로 (8) 의 특별한 사례인

와

V_a0aV_ㅁㅁ → V_aaV_ㅁ0ㅁ

를 적용한다. 그리고 (9) 로부터 얻어진

V_aaV_ㅁ0ㅁ → V_a1aV_ㅁㅁ

를 적용한다. 그리고 나서 유도의 다음 단계들은 다음과 같다.

V_a0aV_aaV_ㅁㅁ ⇒ V_ㅁㅁV_a0aV_ㅁㅁ ⇒ V_aaV_aaV_ㅁ0ㅁ ⇒ V_aaV_a1aV_ㅁㅁ

첫 첨자들의 순서열은 항상 초기 입력을 기억하면서 그대로 남아 있다. 나머지 첨자들의 순서열은 다음과 같고, 이것들은 식 (14) 에서 기술한 순간적 묘사들과 동치이다.

0aaㅁ, a0aㅁ, aa0ㅁ, a1aㅁ

마지막으로, (10) 에서 (13) 까지의 생성규칙들이 다음과 같이 마지막 단계에서 사용된다.

식 (6) 에서 (13) 까지의 식에서 기술된 구성이 다음 결과를 증명하는 기반이 된다.

V_aaV_a1aV_ㅁㅁ ⇒ V_aaaV_ㅁㅁ ⇒ V_aaaㅁ ⇒ aaㅁ ⇒ aa

 정리 7

모든 순환적으로 열거가능한 언어 L 에 대하여, L = L(G) 인 무제한 문법 G 가 존재한다.

증명 : 기술된 구성은 x ┣ y 이면

e(x) ⇒ e(y)

임을 보증한다. 여기서 e(x) 는 주어진 관례에 따른 부호화된 문자열을 나타낸다. 몇 단계의 유도에 의하여 다음과 같은 성질이 성립함을 보일 수 있다 :



이고 오직 그럴 때에만

e(y)

이다.

또한 모든 가능한 시작 상황을 생성할 수 있고, 만일 M 이 종료 상황에 들어가고 오직 그럴 때에만 w 가 적절하게 재구성된다는 것을 보여야 한다. 상세한 증명은 그다지 어렵지 않고, 연습문제로 남겨둔다.

이들 두 가지 정리는 우리가 하려고 제시하였던 것을 확립한다. 이들은 무제한 문법과 연관된 언어군이 순환적으로 열거가능한 언어군과 동일하다는 것을 보여준다.

연습문제

1. 다음의 무제한 문법은 어떤 언어를 유도하는가?

2. 무제한 문법에서 생성규칙의 좌변에 빈 문자열을 허용한다면 어떤 어려움이 발생할 것인가?

3. 임의의 유도에서의 시작점이 단일 변수이기 보다는 문자열들의 유한 집합일 수 있는 문법들의 변형을 고려해 보자. 이러한 개념을 정형화하고, 우리가 여기서 사용하던 무제한 문법과 어떠한 연관성을 가지는지 살펴보아라.

4. 예제 1 에서, 구성된 문법이 b 를 포함하는 어떠한 문자열도 만들 수 없음을 증명하라.

5. 정리 7 의 증명의 세부사항을 보여라.

6. L(01 (01)^*) 을 위한 튜링 기계를 구성하고, 정리 7 에서의 구성방법을 이용하여 무제한 문법을 찾아라. 또한 결과로 얻어진 문법을 이용하여 0101 을 유도하라.

7. 모든 무제한 문법에 대해 아래와 같은 형태의 생성규칙들을 갖는 동치인 무제한 문법이 존재함을 보여라.

        u → v (여기서 u, v ∈ (V ∪ T)⁺ 그리고 |u| ≤ |v| 이다.)

    혹은

        A → λ (여기서 A ∈ V 이다.)

8. |u| ≤ 2 그리고 |v| ≤ 2 라는 조건을 추가해도 연습문제 7 의 결과가 여전히 성립함을 보여라.

9. 어떤 저자는 정의 3 에서 제시한 무제한 문법의 정의와는 다른 정의를 내리기도 한다. 이러한 정의에서 무제한 문법의 생성규칙들은 아래와 같은 형식이기를 요구한다.

        x → y

    여기서

        x ∈ (V ∪ T)^* V(V ∪ T)^*

    이고

        y ∈ (V ∪ T)^*

    이다. 차이는 여기에서 좌변에 적어도 한 개의 변수가 있어야 한다는 것이다.

    이 또 다른 정의가 우리들이 사용하는 것과 근본적으로 같다는 것을, 한 유형의 모든 문법에 대하여 동치인 다른 유형의 문법이 존재한다는 의미로서, 증명하라.

3. 문맥-인식 문법과 언어

제한적인 문맥-자유 문법과 일반적인 무제한 문법 사이에 매우 다양한 "다소 제한적인" 문법들이 정의될 수 있다. 모든 경우들이 흥미 있는 결과를 낳는 것은 아니지만 그중 하나인 문맥-인식 문법은 상당한 관심을 받아왔다. 이 문법은 튜링 기계의 제한된 부류인 선형 한정 오토마타와 관련된 언어를 생성한다.

 정의 4

모든 생성규칙들이 다음과 같은 형태일 경우 문법 G = (V, T, S, P) 를 문맥-인식 문법 (context-sensitive grammar) 이라 한다.

x → y

여기서 x, y ∈ (V ∪ T)⁺ 이고,

|x| ≤ |y|                                                                                (15)

이다.

정의 4 는 분명하게 이와 같은 형식의 문법에 대한 한 가지 단면을 보여준다. 즉, 연속적인 문장 형태의 길이가 결코 감소할 수 없다는 의미로서 비축소적 (noncontracting) 성질을 갖고 있다. 이와 같은 문법을 왜 문맥-인식이라고 하는지 다소 불분명하지만, 모든 이런 형태의 문법들이 모든 생성규칙들이 다음과 같은 형태인 정규형인 형태로 다시 작성될 수 있음을 보일 수 있다 (예로서, Salomaa 1973 을 보시오).

xAy → xvy

이것은 다음과 같은 생성규칙이 왼쪽에는 x 가 있고, 오른쪽에는 y 가 있는 문맥의 상황에서 A 가 나타날 때에만 적용될 수 있다고 말하는 것과 동치이다.

A → v

우리는 이와 같은 특별한 해석에서 유래된 용어를 사용하지만, 여기서 그 형식 자체는 우리에게 관심의 대상이 아니다. 따라서 우리는 정의 4 에 전적으로 의존할 것이다.

(1) 문맥-인식 언어와 선형 한정 오토마타

문맥-인식 문법은 같은 이름을 갖는 언어군과 연관이 된다.

 정의 5

L = L(G) 이거나 L = L(G) ∪ {λ} 인 문맥-인식 문법 G 가 존재한다면 언어 L 을 문맥-인식 언어라 한다.

이 정의에서 빈 문자열을 다시 도입한다. 정의 4 는 x → λ 가 허용되지 않는다는 것을 의미한다. 따라서 문맥-인식 문법은 빈 문자열을 포함하는 언어를 결코 생성할 수 없다. 그러나 λ 를 포함하지 않는 모든 문맥-자유 언어는 문맥-인식 문법의 특별한 경우에 의하여, 말하자면, Chomsky 정규형이나 Greibach 정규형인 문법에 의하여 생성될 수 있다. 두 정규형 모두 정의 4 의 조건들을 만족한다. (문법에는 포함되지 않지만) 문맥-인식 언어의 정의에 빈 문자열을 포함시킴으로써 문맥-자유 언어군이 문맥-인식 언어군의 부분집합이라고 주장할 수 있다.

 예제 2

언어 L = { aⁿbⁿcⁿ : n ≥ 1 }은 문맥-인식 언어이다. 우리는 이 언어에 대한 문맥-인식 문법을 보임으로써 이것을 증명한다. 그런 문법의 하나는 다음과 같다.

S → abc|aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa|aaA

a³b³c³ 의 유도를 살펴봄으로써 이와 같은 문법이 어떻게 작동하는지를 알 수 있다.

S ⇒ aAbc ⇒ abAc ⇒ abBbcc
   ⇒ aBbbcc ⇒ aaAbbcc ⇒ aabAbcc
   ⇒ aabbAcc ⇒ aabbBbccc
   ⇒ aabBbbccc ⇒ aaBbbbccc
   ⇒ aaabbbccc

이 해답은 변수 A 와 B 를 전달자 (messenger) 로서 효율적으로 사용하였다. A 는 왼쪽에서 생성되고 최초의 c 오른쪽으로 이동하였고, 여기서 또 다른 b 와 c 를 생성한다. 그리고 나서 대응되는 a 를 생성하기 위하여 전달자 B 를 왼쪽으로 다시 보낸다. 이와 같은 과정은 튜링 기계가 언어 L 를 인식하도록 프로그램하는 방법과 매우 유사하다.

위 예제의 언어는 문맥-자유 언어가 아니기 때문에 문맥-자유 언어군은 문맥-인식 언어군의 진부분 집합이라는 것을 알 수 있다. 또한 예제 2 로부터 상대적으로 간단한 예라할지라도 문맥-인식 문법을 찾아내는 것이 쉬운 일이 아니라는 것을 알 수 있다. 가끔은 튜링 기계 프로그램으로 시작하여 그것과 동치인 문법을 찾아냄으로써 그 해답을 아주 쉽게 얻을 수 있다. 몇 개의 예들에서 언어가 문맥-인식 언어일 때마다 대응하는 튜링 기게는 예상할 수 있는 공간을 필요로 한다는 것을 보일 것이다. 실제로 이것은 선형 한정 오토마타로 간주될 수 있다.

 정리 8

λ 를 포함하지 않는 모든 문맥-인식 언어 L 에 대하여 L = L(M) 인 선형 한정 오토마타 M 이 존재한다.

증명 : L 이 문맥-인식 언어라면, L - {λ} 에 대한 문맥-인식 문법이 존재한다. 이 문법에서의 유도가 선형 한정 오토마타에 의하여 시뮬레이션될 수 있다는 것을 보인다. 선형 한정 오토마타는 두 개의 트랙을 갖는다. 하나는 입력 문자열 w 를 포함하고 다른 하나는 문법 G 를 사용하여 유도되는 문장 형태를 포함한다. 이 논의의 핵심은 어떠한 문장 형태라도 |w| 보다 큰 길이를 가질 수 없다는 것이다. 주목해야 할 또 다른 요점은 선형 한정 오토마타는 정의에 의하여 비결정적이라는 것이다. 항상 올바른 생성규칙이 가정될 수 있고 비생산적인 다른 규칙들은 추구되어서는 안 된다고 주장할 수 있기 때문에, 비결정적이라는 요점은 논의에 있어서 반드시 필요하다. 그러므로 정리 6 에서 기술된 계산은 원래 w 가 차지한 공간 이외의 공간을 사용하지 않고 수행될 수 있다. 즉, 선형 한정 오토마타에 의하여 수행될 수 있다.

 정리 9

언어 L 이 어떤 선형 한정 오토마타 M 에 의하여 인식된다면, L 을 생성하는 문맥-인식 문법이 존재한다.

증명 : 여기서의 구성은 정리 7 의 구성과 유사하다. 정리 7 에 의하여 생성된 모든 생성규칙은 (13) 의

ㅁ → λ

을 제외하고 모두 비축소적이다. 그러나 이 생성규칙은 생략될 수 있다. 이것은 튜링 기계가 원래 입력의 범위를 벗어나서 이동할 때만이 필요한 것이고 이 경우에는 필요치 않다. 이와 같은 불필요한 생성규칙을 포함하지 않는 구성에 의하여 얻어진 문법은 비축소적이다. 따라서 정리 9 의 논의를 종결한다.

(2) 순환적인 언어와 문맥-인식 언어들 사이의 관계

정리 9 는 모든 문맥-인식 언어가 어떤 튜링 기계에 의해 승인되고 따라서 순환적으로 열거가능함을 말한다. 이 정리로부터 정리 10 은 쉽게 얻어진다.

 정리 10

모든 문맥-인식 언어 L 은 순환적이다.

증명 : 연관된 문맥-인식 문법 G 를 갖고 있는 문맥-인식 언어 L 을 고려하고 다음과 같은 w 의 유도를 살펴보자.

일반성을 잃지 않고, 단일 유도에서 모든 문장 형태들은 서로 다르다고 가정한다. 즉, 모든 i ≠ j 에 대하여 이다. 논의의 요점은 어떤 유도에서 단계의 수는 |w| 의 한정 함수 (bounded function) 라는 것이다. G 는 비축소이기 때문에,

임을 알 수 있다. 한 가지 추가해야 할 사실은, 오직 G 와 w 에 종속되는, 다음 성질을 만족하는 m 이 존재한다는 것이다 : 모든 j 에 대하여, |V ∪ T| 와 |w| 의 한정 함수 m = m (|w|) 를 갖고, 이다.

이것은 |V ∪ T| 이 유한하기 때문에 주어진 길이의 문자열들은 오직 유한 개만 있다는 사실에 의하여 성립한다. 그러므로 w ∈ L 의 유도의 길이는 길어야 |w|m(|w|) 이다.

이와 같은 관찰에 의하여 L 에 대한 소속성 알고리즘을 얻을 수 있다. 길이가 길어야 |w|m(|w|) 까지인 모든 유도를 검사해 본다. G 의 생성규칙 집합이 유한하기 때문에, 그런 유도들은 단지 유한 개만 있다. 그들 중에 어느 하나가 w 를 유도하면 w ∈ L 이고, 그렇지 않으면 이다.

 정리 11

문맥-인식 언어가 아닌 순환적인 언어가 존재한다.

증명 : T = {a, b} 에 대한 모든 문맥-인식 문법들의 집합을 고려해 보자. 각 문법이 다음과 같은 변수 집합을 갖는 관례를 사용할 수 있다.

모든 문맥-인식 문법은 각각의 생성규칙에 의하여 완전히 명시된다. 즉, 이 생성규칙들을 다음과 같이 하나의 문자열로 생각할 수 있다.

이 문자열에 대하여 다음과 같은 준동형 (homomorphism) 을 적용한다.

h(a) = 010

h(b) = 01²0

h(→) = 01³0

h(;) = 01⁴0

h(V_i) = 01ⁱ⁺⁵0

그러므로 임의의 문맥-인식 문법은 L((011^* 0)^*) 에 속한 문자열에 의하여 유일하게 표현될 수 있다. 더욱이, 주어진 임의의 그런 문자열에 대하여, 대응되는 문맥-인식 문법이 많아야 하나가 있다는 의미에서, 그와 같은 표현은 거꾸로 전환이 가능하다.

{0, 1}⁺ 에 대한 고유 순서를 도입한다. 따라서 문자열들을 등과 같은 순서로 작성할 수 있다. 주어진 문자열 가 문맥-인식 문법을 정의하지 못할지도 모른다. 만일 정의한다면 그 문법을 라 한다. 그리고 나서 다음과 같이 언어 L 을 정의한다.

L = {w_i : w_i 가 문맥-인식 문법 G_i 를 정의하고 이다.}

L 은 잘 정의되고 실제로 순환적인 언어이다. 이것을 확인하기 위하여 소속성 알고리즘을 구성한다. 주어진 에 대하여  가 문맥-인식 문법 를 정의하는지 검사한다. 만일 정의하지 않으면 이다. 문자열이 문법을 정의한다면 는 순환적이고, 인지 알아내기 위하여 정리 10 의 소속성 알고리즘을 이용할 수 있다. 만일 이 아니라면, 는 L 에 속한다.

그러나 L 은 문맥-인식이 아니다. 만일 그렇다면, 를 만족하는 가 존재할 것이다. 그러면 가 에 속하는지 알아볼 수 있다. 이라고 가정한다면 정의에 의하여 는 L 에 속하지 않는다. 그러나 이고 따라서 이것은 모순이 된다. 반대로, 이라고 가정한다면 정의에 의하여 이고 이것은 또 다른 모순이 된다. 그러므로 L 이 문맥-인식이 아니라는 결론에 도달하게 된다.

정리 11 의 결과는 선형 한정 오토마타가 실제로 튜링 기계보다 강력하지 않다는 것을 보여주고 있다. 왜냐하면 선형 한정 오토마타는 단지 순환적인 언어들의 진부분 집합만을 인식하기 때문이다. 이것은 선형 한정 오토마타가 푸시다운 오토마타보다 훨씬 강력하다는 것과 똑같은 당연한 결과이다. 문맥-자유 문법에 의하여 생성되는 문맥-자유 언어들은 문맥-인식 언어들의 부분집합이다. 여러 가지 예제들에 의하여 밝혀진 바와 같이, 이들은 진부분 집합이다. 한편으로 선형 한정 오토마타와 문맥-인식 언어의 동치성과 다른 한편으로는 푸시다운 오토마타와 문맥-자유 언어의 동치성 때문에, 푸시다운 오토마타에 의하여 인식되는 모든 언어는 선형 한정 오토마타에 의해서도 역시 인식될 수 있다는 것을 알 수 있다. 그러나 어떠한 푸시다운 오토마타에 의해서도 인식되지 않지만, 어떤 선형 한정 오토마타에 의해서는 인식될 수 있는 언어들이 존재한다는 것을 알 수 있다.

연습문제

1. 아래의 언어에 대한 문맥-인식 문법을 찾아라.

        (a)

        (b)

        (c)

        (d)

2. 아래의 언어에 대한 문맥-인식 문법을 찾아라.

        (a)

        (b)

3. 문맥-인식 언어군은 합집합에 대해 폐포 성질이 성립함을 보여라.

4. 문맥-인식 언어군은 전도에 대해 폐포 성질이 성립함을 보여라.

5. 정리 10 의 m 에 대해서, |w| 와 |V ∪ T| 의 함수로서 m 에 대한 분명한 한계를 제시하라.

6. 언어 L = {wuw : w, u ∈ {a, b}⁺} 에 대한 문맥-인식 문법이 존재함을 보여라. 문법을 명확하게 구성할 필요는 없다.

4. Chomsky 계층

지금까지 여러 가지 언어군들을 살펴보았다. 순환적으로 열거가능한 언어 , 문맥-인식 언어 , 문맥-자유 언어 , 정규 언어 등이 여기에 해당한다. 이 언어군들 사이의 관계를 나타내는 한 가지 방법이 Chomsky 계층이다. 형식 언어 이론의 창시자인 Noam Chomsky 는 초기에 언어들을 네 가지 언어 형식들, type 0, type 1, type 2, type 3 으로 분류하였다. 이 원래의 용어가 지속되어 왔고, 사람들이 그것을 자주 참조하지만, 번호로 매겨진 형식은 실제로 우리가 연구하였던 언어군들에 대한 다른 이름들이다. type 0 언어는 무제한 문법에 의하여 생성되는 언어들이다. 즉, 순환적으로 열거가능한 언어이다. type 1 은 문맥-인식 언어들로 구성되고, type 2 는 문맥-자유 언어들로 구성되며, type 3 은 정규 언어들로 구성된다. 우리가 살펴본 바와 같이 type i 의 각 언어군은 type i - 1 언어군의 진부분 집합이다. 그림 3 의 다이어그램은 이들 사이의 관계를 명확히 보여준다. 그림 3 이 원래의 Chomsky 계층을 보여준다. 우리는 또한 이 그림에 끼어 넣을 수 있는 여러 가지 다른 언어군들을 살펴보았다. 결정적 문맥-자유 언어군 과 순환적인 언어군 들을 포함하여 그림 14 와 같이 확장된 계층을 얻을 수 있다.

그림 3

그림 4

다른 언어군들이 정의될 수 있고 그림 4 에서의 그들의 위치가 연구될 수 있다. 그러나 그들의 관계가 항상 그림 3 과 4 와 같이 깔끔하게 포함되는 구조를 갖지 않을 수도 있다. 어떤 경우에 있어서는 그 관계가 완전하게 이해될 수 없는 것도 있다.

 예제 3

앞에서 다음과 같은 문맥-자유 언어를 소개하였고 이 언어는 결정적 문맥-자유 언어이지만 선형 언어는 아니라는 것을 살펴보았다.

반면에 다음 언어는 선형 언어이지만 결정적 문맥-자유 언어는 아니다.

이 예들은 그림 5 에 보여진 것과 같은 정규 언어, 선형 언어, 결정적 문맥-자유 언어, 그리고 비결정적 문맥-자유 언어들 사이의 관계를 나타낸다.

그림 5

여기에는 지금까지 해결되지 않은 문제가 있다. 우리는 10.5 절의 연습문제 8 에서 결정적 선형 한정 오토마타의 개념을 소개하였다. 여기서 다른 오토마타와 연관하여 질문했던 문제들을 물오볼 수 있다. 즉, 비결정성이 여기서 어떤 역할을 하는가? 불행하게도 어떤 쉬운 답도 없다. 지금까지 결정적 선형 한정 오토마타에 의하여 인식되는 언어군이 문맥-인식 언어들의 진부분 집합인지는 알려지지 않았다.

요약하면, 지금까지 여러 가지 언어군들과 연관돈 오토마타들의 관계를 살펴보았다. 그렇게 함으로써 언어들의 계층과 언어에 대한 인식기로서 그들의 능력에 따라 오토마타를 분류하였다. 튜링 기계가 선형 한정 오토마타보다 강력하고 또한 선형 한정 오토마타는 푸시다운 오토마타보다 훨씬 강력하다. 계층의 맨 밑에는 우리가 연구를 시작하였던 유한인식기가 있다.

연습문제

1. 그림 4 에 나타낸 포함 관계가 진부분 집합 관계라는 것을 보여주는 이 책에서 주어진 예들을 모아라.

2. 선형이지만 결정적 문맥-자유가 아닌 언어의 예를 두 개만 찾아라 (예제 3 의 언어는 제외).

3. 결정적 문맥-자유이지만 선형이 아닌 언어의 예를 두 개만 찾아라 (예제 3 의 언어는 제외).