형식언어 계층과 오토마타

(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. 순환적 언어와 순환적으로 열거가능한 언어

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

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

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

만일 언어 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) 순환적으로 열거가능하지 않은 언어들

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

그림 2

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

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

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

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

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

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

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

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

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

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

연습문제

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 에서 생성규칙은 아무 형태나 취할 수 있도록 허용되었다. 그리고 나서 특별한 문법 형태를 얻기 위하여 여러 가지 제약들이 가해졌다. 만일 일반적인 형태를 취하고 아무런 제약도 가해지지 않는다면 이 문법을 무제한 문법이라 한다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

연습문제

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

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

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

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

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

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

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

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

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

정리 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 와 같이 깔끔하게 포함되는 구조를 갖지 않을 수도 있다. 어떤 경우에 있어서는 그 관계가 완전하게 이해될 수 없는 것도 있다.

그림 5

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

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

연습문제

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

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

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