유한 오토마타

 

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

 

1. 결정적 유한 인식기

     (1) 유한 인식기와 전이 그래프

     (2) 언어와 Dfa

     (3) 정규 언어

     연습문제

2. 비결정적 유한 인식기

     (1) 비결정적 인식기의 정의

     (2) 비결정성을 사용하는 이유

     연습문제

3. 결정적 유한 인식기와 비결정적 유한 인식기의 동치성

     연습문제

4. 유한 오토마타에서의 상태의 수 축소

     연습문제

 

제 1 장에서는 계산에 대한 기본적인 개념을, 특히 오토마타에 대한 논의를, 간략하게 그리고 비형식적으로 소개하였다. 현재 독자들은 오토마타란 무엇인가하는 점과 이를 그래프로 표현하는 방법 등에 대한 일반적인 이해만을 가지고 있을 것이다. 앞으로는 좀더 명확히 하고, 형식적인 정의를 제시하고 그리고 좀더 엄밀한 결과들을 개발하여야 할 것이다. 우선 앞장에서 소개된 일반적인 스킴의 간단한 특정 경우인 유한 인식기 (finite accepter) 를 논의해 보자. 이러한 형태의 오토마타는 임시 기억장소를 갖지 않으며, 입력 파일의 내용을 고쳐 쓰거나 저장할 수가 없기 때문에 계산이 진행되는 동안 필요한 정보를 저장하는 데 엄격한 한계를 갖게 된다. 오토마타의 제어장치를 특정 상태에 놓이게 함으로써 유지할 수 있는 정보의 양이 유한하고, 그리고 상태의 수도 유한하므로, 유한 오토마타는 임의의 순간에 저장되는 정보의 양이 엄격하게 한정되는 상황만을 처리할 수 있다. 예제 16 에서의 오토마타는 이와 같은 유한 인식기의 한 예이다.

1. 결정적 유한 인식기

우리가 구체적으로 공부할 오토마타의 첫 번째 연산 과정이 결정적으로 진행되는 유한 인식기이다. 우선 결정적 유한 인식기에 대한 형식적이고 명확한 정의부터 살펴보도록 한다.

(1) 유한 인식기와 전이 그래프

결정적 유한 인식기는 다음과 같은 방식으로 동작한다. 이 오토마타는 처음에 초기 상태 q0 에 있는 것으로 가정하며, 입력 장치는 입력 문자열의 가장 왼쪽 심볼에 놓여 있다. 오토마타의 매이동마다, 입력 장치는 입력 문자열의 가장 왼쪽 심볼에 놓여 있다. 오토마타의 매이동마다, 입력 장치는 한 자리씩 오른쪽으로 이동한다. 즉 입력 문자를 하나씩 읽어들인다. 입력 문자열의 맨 끝에 도달했을 경우, 오토마타가 종료 상태에 있으면 해당 문자열이 승인되고, 그렇지 않으면 그 문자열은 거부된다. 입력 메커니즘은 오직 왼쪽부터 오른쪽으로 이동할 수 있고, 각 단계마다 정확히 한 심볼만 읽어들인다. 하나의 내부 상태로부터 다른 상태로의 전이는 전이 함수 δ 에 따라 결정된다. 예를 들어, 다음과 같은 전이가 있고

dfa 가 상태 q0 에 있고, 현재 입력 심볼이 a 인 경우 이 dfa 는 상태 q1 으로 전이할 것이다.
오토마타에 대해 논의하는 데 있어서 이에 대한 명확하고 직관적인 이해를 갖는 것이 필수적이다. 유한 오토마타를 가시적으로 표현하기 위해서 보통 전이 그래프 (transition graph) 를 사용한다. 전이 그래프에서의 정점은 상태를 나타내며, 간선은 전이를 나타낸다. 정점의 라벨은 상태의 이름이며, 간선의 라벨은 입력 심볼의 현재값이 된다. 예를 들어, q0 와 q1 이 어떤 dfa M 의 내부 상태들일 경우 M 에 대한 그래프에는 라벨 q0 를 갖는 정점과 라벨 q1 을 갖는 정점들이 존재하게 된다. 라벨 a 를 갖는 간선 (q0, q1) 은 전이 δ(q0, a) = q1 을 표현한다. 초기 상태는 라벨이 붙지 않은 외부로부터 진입하는 간선에 의해 지정되며, 종료 상태는 이중 원 (double circle) 으로 표시한다.

그림 1

좀더 형식적으로, M = (Q, Σ, δ, q0, F) 가 결정적 유한 인식기인 경우 이에 대한 전이 그래프 GM 은 정확히 |Q| 개의 정점을 가지며, 각 정점에는 서로 다른 라벨 qf ∈ F 를 갖는 정점들이 종료 정점(final vertex)이다. 정의 (Q, Σ, δ, q0, F) 로부터 전이 그래프를 구성하는 것은 아주 쉬운 일이고, 그 반대도 역시 쉬운 일이다.

때로는 확장 전이 함수 (extended transition function) 를 도입하는 것이 편리한 경우가 있다. 이 함수 의 두 번째 인수는 단일 심볼이 아닌 문자열이며, 함수값은 오토마타가 주어진 문자열을 모두 읽은 후에 놓이게 되는 상태이다. 예를 들어,

    

이고

    

이면, 다음이 성립한다.

    

형식적으로, 모든 q ∈ Q, w ∈ , a ∈ Σ 에 대해 는 다음과 같이 순환적으로 정의될 수 있다.

                                                                                        (1)

                                                                         (2)

이 정의가 올바르다는 것을 확인하기 위해서, 위의 간단한 예를 정의에 적용해 보자. 우선 식 (2) 를 사용하여 다음을 얻을 수 있다.

                                                                         (3)

그리고 다음을 얻는다.

    

이를 다시 식 (3) 에 대입하면 다음의 기대한 결과를 얻게 된다.

    

(2) 언어와 Dfa

위에서 인식기에 대한 명확한 정의를 하였으며, 이제 관련된 언어가 무엇을 의미하는가를 형식적으로 정의할 준비가 되었다. 이 언어는 분명히 주어진 오토마타에 의해 승인되는 모든 문자열들의 집합일 것이다.

이러한 예들을 보면 전이 그래프가 유한 오토마타를 다루는 데에 얼마나 편리한지를 알 수 있다. 오토마타와 관련한 모든 사항을 엄격하게 전이 함수나 식 (1) 과 (2) 에서 보인 확장 전이 함수 등의 성질을 기반으로 논증할 수도 있으나, 이와 같은 형태의 설명은 이해하기가 쉽지 않다. 따라서 이 책에서는 가능하면 그래프를 사용함으로써 독자들로 하여금 좀더 직관적으로 이에 대한 이해를 할 수 있도록 하고자 한다. 이를 위해서는, 물론 표현에 의한 오해가 없어야 하며 또한 그래프에 기반한 논증이 전이 함수 δ 의 형식적인 성질을 사용한 논증만큼 정당함을 확신할 수 있어야 한다. 다음 정리에 의해 우리는 이러한 확신을 얻을 수 있게 된다.

그림 2

다시금, 이 정리의 결과는 증명이 필요 없을 정도로 지극히 자명하다. 그럼에도 불구하고 자세한 증명을 제시한 이유에는 두 가지가 있다. 그 첫 번째는 이 증명이 간단하지만 오토마타와 관련하여 필요한 귀납법 증명의 대표적인 예가 되기 때문이며, 두 번째는 이 정리의 결과가 앞으로 계속 사용되기 때문에 이를 정리로 증명해 둠으로써 이후에 우리가 그래프를 사용하여 자신있게 논의할 수 있게 해준다. δ 의 성질보다는 그래프를 사용하는 것이 각종 예제들이나 증명을 더욱 명확하게 한다.

그래프가 오토마타를 가시화하는 데 편리하지만, 다른 표현방법들도 또한 유용하다. 예를 들면, 전이 함수 δ 를 테이블로 표현할 수 있다. 그림 3 의 테이블은 그림 2 와 동치이다. 이 테이블에서 행은 현재 상태를 표시하고 열은 입력 심볼을 나타낸다. 또한, 이 테이블의 각 엔트리는 다음 상태를 정의한다.

 

a

b

그림 3

이 예로부터 dfa 는 컴퓨터 프로그램으로 예를 들어, 테이블 탐색이나 또는 일련의 "if" 문장들로, 쉽게 구현될 수 있음이 명백하다. 물론 가장 좋은 구현방법이나 표현방법은 특정 응용 분야에 따라 결정될 수 있을 것이다. 이 책에서 우리가 하고자 하는 논의에 대해서는 전이 그래프가 가장 적절하며, 따라서 대부분의 경우 전이 그래프를 사용할 것이다.

비형식적으로 정의된 언어에 대한 오토마타를 구성하는 데 있어 우리는 고급언어로 프로그래밍하는 것과 같은 추론 방법을 사용한다. 하지만, dfa 와 같은 오토마타는 강력한 기능을 거의 갖지 않고 있기 때문에 dfa 의 프로그래밍이 지루하기도 하며 때에 따라서는 개념적으로 복잡하기도 할 것이다.

그림 4

그림 5

(3) 정규 언어

모든 유한 오토마타는 특징 언어를 인식하게 된다. 모든 가능한 유한 오토마타들을 고려해 보면 이들과 관련된 언어들의 집합을 얻을 수 있다. 이러한 언어들의 집합을 언어군 (family) 이라 부를 것이다. 결정적 유한 오토마타에 의해 인식되는 언어군은 극히 제한되어 있다. 이 언어군에 속하는 언어들의 구조와 성질들은 이후 공부를 해 나가면서 분명해질 것이며, 우선 이 언어군에 이름을 부여하기로 하자.

 

그림 6

그림 7

마지막 예제를 보면 임의의 언어 L 이 정규 언어일 때 등도 모두 정규 언어가 될 것임을 짐작해 볼 수도 있다. 이에 대한 형식적인 증명은 이후에 보게 될 것이다.

연습문제

1. 문자열 0001, 01001, 0000110 가운데 그림 1 의 dfa 에 의해 승인되는 문자열들은 어느 것인가?

2. Σ = {a, b} 에 대해, 다음의 문자열들로 이루어진 언어를 인식하는 dfa 를 구성하라.

        (a) a 를 하나만 갖는 모든 문자열들

        (b) a 를 적어도 하나이상 갖는 모든 문자열들

        (c) a 가 세 번 이하로 나타나는 모든 문자열들

        (d) a 가 적어도 한 번 이상, 그리고 b 가 정확히 두 번 나타나는 모든 문자열들

        (e) a 가 정확히 두 번, 그리고 b 가 세 번 이상 나타나는 모든 문자열들

3. 그림 6 에서 를 비종료 상태로 하고 를 종료 상태로 바꾸었을 경우, 이 dfa 가 를 인식함을 보여라.

4. 앞의 연습문제 3 에서 보인 결과를 일반화시켜 보아라. 즉, 이고 이라 했을 때 임을 보여라.

5. 다음 언어에 대한 dfa 를 구성하라.

        (a)

        (b)

6. 다음 다이어그램에서 보인 오토마타에 의해 인식되는 언어를 집합 표현방법으로 기술하라. 이 언어의 특성을 말로 간단히 제시해 보아라.

7. Σ = {a, b} 에 대한 다음 언어들을 인식하는 dfa 를 구성하라.

        (a) L = {w : |w| mod 3 = 0}

        (b) L = {w : |w| mod 5 ≠ 0}

        (c)

        (d)

        (e)

        (f)

8. 한 문자열 내의 런 (run) 이란 가능한 한 같은 심볼들로만 이루어지고, 길이가 2 이상인 부문자열을 의미한다. 예를 들어, 문자열 abbbaab 는 길이가 3 인 b 의 런과 길이가 2 인 a 의 런을 포함하고 있다. 알파벳 {a, b} 에 대한 다음 언어들에 대한 dfa 를 구성하라.

        (a) L = {w : w 는 길이가 4 미만인 런을 포함하지 않는다}

        (b) L = {w : 모든 a 의 런은 길이가 2 또는 3 이다}

        (c) L = {w : 길이가 3 인 a 의 런이 최대 두 개가 존재한다}

        (d) L = {w : 길이가 3 인 a 의 런이 정확히 두 개가 존재한다}

9. 다음과 같은 특성을 갖는 {0, 1} 에 대한 문자열들의 집합을 고려해 보자. 각각에 대해 이를 인식하는 dfa 를 구성하라.

        (a) 모든 부문자열 00 뒤에는 1 이 존재한다. 예를 들어, 문자열 101, 0010, 0010011001 등은 이 언어에 속하지만, 문자열 0001 과 00100 은 이 언어에 속하지 않는다.

        (b) 00 은 포함하지만 000 은 포함하지 않는다.

        (c) 가장 왼쪽 심볼과 가장 오른쪽 심볼이 서로 다르다.

        (d) 길이가 4 인 모든 부문자열은 최대 두 개의 0 을 갖는다. 예를 들어, 001110 과 011001 은 이 언어에 속하지만, 10010 은 이 언어에 속하지 않는다 (부문자열 0010 이 세 개의 0 을 갖기 때문).

        (e) 길이가 5 이상인 문자열이면서 오른쪽 끝에서 4 번째 심볼이 가장 왼쪽 심볼과 서로 다르다.

        (f) 가장 왼쪽의 두 개 심볼이 가장 오른쪽의 두 개 심볼과 같은 모든 문자열

10. {0, 1} 에 대한 문자열로서 이를 정수의 이진 표현으로 보았을 때 5 로 나누어 나머지가 0 인 모든 문자열들을 승인하는 dfa 를 보여라. 예를 들어, 0101 (정수 5) 과 1111 (정수 15) 은 이 dfa 에 의해 승인된다.

11. 이 정규 언어임을 보여라.

12. 이 정규 언어임을 보여라.

13. 이 정규 언어임을 보여라.

14. 이 정규 언어임을 보여라.

15. C 언어에서의 모든 실수들의 집합이 정규 언어임을 보여라.

16. L 이 정규 언어일 경우, L - {λ} 도 정규 언어임을 보여라.

17. 식 (1) 과 (2) 를 사용하여, 모든 에 대해 다음이 성립함을 보여라.

        

18. L 을 그림 2 에서 보인 오토마타에 의해 인식되는 언어라 하자. 을 인식하는 dfa 를 구성하라.

19. L 을 그림 2 에서 보인 오토마타에 의해 인식되는 언어라 하자. 을 인식하는 dfa 를 구성하라.

20. L 을 예제 5 에서의 오토마타에 의해 인식되는 언어라 하자. 가 정규 언어임을 보여라.

21. 을 어떤 dfa M 에 대한 전이 그래프라 하자. 다음을 증명하라.

        (a) 언어 L(M) 이 무한 (infinite) 일 경우, 에 적어도 하나 이상의 사이클이 존재하며, 시작 정점에서 이 사이클 내의 어떤 정점으로 가는 경로와 이 사이클 내의 어떤 정점으로부터 한 종료 정점으로 가는 경로가 반드시 존재한다.

        (b) 언어 L(M) 이 유한 (finite) 일 경우, 위와 같은 사이클이 존재하지 않는다.

22. 문자열에서 가장 오른쪽 심볼을 제거하는 연산을 truncate 라 하자. 예를 들어, truncate (aaaba) 는 aaab 가 된다. 이 연산을 언어 수준으로 확장하면 다음과 같이 정의할 수 있다.

        truncate(L) = {truncate(w) : w ∈ L}

      임의의 정규 언어 L 에 대한 dfa 가 주어졌을 때, truncate(L) 에 대한 dfa 를 구성할 수 있음을 보여라. 이를 이용하여, 언어 L 이 λ 를 포함하지 않는 정규 언어일 때 truncate(L) 역시 정규 언어임을 증명하라.

23. 예제 17 에서 정의된 바와 같은 이진수들이라 하자. 다음과 같은 세 원소 쌍 (triplets) 의 문자열들의 집합이 정규 언어임을 보여라.

        

     여기서 들은 x + y = z 를 만족한다.

24. 주어진 dfa 에 의해 인식되는 언어는 유일하지만, 일반적으로 하나의 언어를 인식하는 dfa 는 여러 개가 존재한다. 그림 4 에서의 dfa 가 인식하는 언어와 같은 언어를 인식하면서 정확히 6 개의 상태를 갖는 dfa 를 구성하라.

2. 비결정적 유한 인식기

유한 인식기들이 비결정적으로 작동하도록 허락할 경우, 이들은 더욱 복잡해진다. 비결정성은 매우 강력한 기능이기는 하지만, 평범한 개념은 아니다. 일반적으로 컴퓨터 시스템은 완전히 결정적이고, 선택한다는 요소는 부적절하여 보인다. 그럼에도 불구하고, 비결정성 (nondeterminism) 은 매우 유용한 개념이며, 앞으로 공부하면서 확인할 것이다.

(1) 비결정적 인식기의 정의

비결정성은 오토마타의 이동에 있어서 선택을 할 수 있음을 의미한다. 각 상황에서 유일한 이동만을 규정하기 보다 가능한 여러 가지 이동들의 집합을 허용하는 것이다. 형식적으로, 이는 오토마타의 전이 함수가 상태들의 집합을 치역 (range) 으로 갖게 함으로써 가능해진다.

위 정의와 dfa 에 대한 정의 사이에는 크게 세 가지 차이점이 존재한다. 비결정적 인식기에서는 δ 의 치역은 멱집합 2Q 내에 있으며, 따라서 그 값이 Q 의 단일 원소가 아닌 Q 의 부분집합이 된다. 이 부분집합은 해당 전이에 의해 도달할 수 있는 모든 가능한 상태들의 집합이 되는 것이다. 예를 들어, 만일 현재 상태가 q1 이고 이 상태에서 심볼 a 가 읽혀지고, 전이 함수가 다음과 같다면,

q0 나 q2 가 이 nfa 의 다음 상태가 될 수 있는 것이다. 또한, nfa 에서는 전이 함수 δ 의 두번째 인수로 λ 를 허용한다. 이는 nfa 가 입력 심볼을 읽지 않고도 상태 전이를 할 수 있음을 의미한다. 지금까지의 입력 장치는 오른쪽으로 움직이는 것만이 가능했지만, 어떤 이동에서는 입력 포인터가 머물러 있는 것이 가능하다. 마지막으로 nfa 에서는 집합 δ(qi, a) 가 공집합일 수 있으며, 이런 특정 상황에 대하여 정의된 전이가 없음을 의미한다.
dfa 에서와 마찬가지로 비결정적 인식기도 전이 그래프에 의해 표현될 수 있다. 전이 그래프의 정점들은 Q 에 의해 결정되며, δ(qi, a) 가 qj 를 포함할 경우만 라벨 a 를 갖는 간선 (qi, qj) 가 존재한다. 이때 a 는 빈 문자열일 수도 있으며, 따라서, 라벨 λ 를 갖는 간선들도 존재할 수 있다.
어떤 문자열에 대해, 이 문자열이 모두 처리된 후에 오토마타를 종료 상태에 놓이게 하는 이동 순서가 존재하면, 이 문자열은 nfa 에 의해 승인된다. 종료 상태에 도달될 수 있는 이동 순서가 전혀 존재하지 않으면, 해당 문자열은 거부된다(즉, 승인되지 않는다). 따라서, 비결정성은 각 상태에서 (nfa 가 모든 문자열들을 승인하고자 한다는 가정하에) 최상의 이동이 선택되도록 하는 직관적인 통찰력과 관련되어 있다고 생각할 수 있다.

그림 8

그림 9

그림 10

라벨이 주어진 보행을 이용하여 확장 전이 함수 를 정의하는 것은 약간 비형식적일 수도 있으며, 따라서 이에 대해서 좀더 자세히 살펴볼 필요가 있다. 임의의 정점 사이에 라벨 w 의 보행이 있거나 없거나 둘 중의 하나이기 때문에, 는 완전하게 정의된다고 볼 수 있으며, 따라서 정의 5 는 적절하다고 할 수 있다. 이와 관련하여 아마도 확인하기 좀더 어려운 사실은 를 구하는 데 이 정의가 항상 사용될 수 있다는 것이다.

수학적 개요 및 표기법에서, 우리는 그래프의 두 정점간에 존재하는 모든 단순 경로들을 구하는 알고리즘을 소개했었다. 예제 9 에서 보였듯이 라벨이 주어진 보행이 항상 단순 경로는 아니기 때문에, 이 알고리즘을 그대로 사용할 수는 없지만, 우리는 정점이나 간선이 중복되는 경우에도 적용되도록 알고리즘을 수정할 수 있다. 이 새로운 알고리즘은 길이가 1, 2, 3, .... 인 모든 보행들을 연속적으로 찾아낼 것이다.

한 가지 더 남아 있는 어려운 문제는 w 가 주어졌을 때 라벨 w 를 갖는 보행의 길이가 얼마나 길어질 수 있는가 하는 점이다. 이를 알아내기가 그리 쉽지는 않다. 예제 9 에서 사이의 라벨 a 를 갖는 보행의 길이는 4 이다. 문제는 라벨에 영향을 주지 않으면서 보행의 길이만 길어지게 하는 λ-전이에 의해 발생한다. 이 상황은 다음과 같은 관찰에 의해 수고를 덜 수 있다. 두 정점 사이에 라벨 w 인 보행이 존재한다면, 길이가 A + (1 + Λ) |w| 이하인 보행이 존재한다. Λ 는 해당 그래프 내의 λ-간선들이 λ 가 아닌 라벨을 갖는 간선에 의해 분리될 수 있는 보행이 존재한다. 그렇지 않은 경우에는 해당 보행이 라벨 λ 를 갖는 사이클을 가지게 된다. 이와 같은 사이클은 해당 보행의 라벨에 영향을 주지 않고 단순 경로로 대치될 수 있다. 이에 대한 형식적인 증명은 연습문제로 남겨 두기로 한다.

이런 관찰에 따라, 우리는 를 계산하는 방법을 생각해 볼 수 있다. 정점 에서 출발하는 길이가 Λ + (1 + Λ) |w| 이하인 보행들을 모두 구한다. 이들로부터 라벨이 w 인 보행들을 선택한다. 그러면 선택된 보행들의 종료 정점들이 집합 의 원소가 된다.

이미 앞에서 언급했듯이, 를 결정적 오토마타에서와 같이 순환적인 방법으로 정의할 수 있다. 하지만, 아쉽게도 이러한 정의는 그리 명백하지 않고, 이렇게 정의된 확장 전이 함수를 사용한 증명들은 이해하기가 어렵다. 따라서 우리는 정의 5 에서 주어진 보다 직관적이고, 이해하기 쉬운 정의를 사용하기로 한다.

앞에서 기술한 dfa 에서와 마찬가지로, nfa 에 의해 인식되는 언어 역시 확장 전이 함수에 의해 정의된다.

(2) 비결정성을 사용하는 이유

비결정적 기계에 대해 논의할 때에는, 객관적인 개념을 사용하는 데에 조심해야 한다. 직관을 잘못 사용할 경우 많은 개념들이 혼란스러워질 수 있으므로, 우리는 어떤 결론을 실증하기 위하여 명확한 논증을 제시할 수 있어야 한다. 비결정성은 매우 어려운 개념이다. 디지털 컴퓨터는 완벽하게 결정적이다 : 즉, 어떤 시점에도 이들의 상태는 초기 상태와 입력에 따라 정확히 예측될 수 있다. 따라서, 우리가 왜 비결정적 오토마타에 대해 공부하는지에 대한 의문이 자연스럽게 생길 수 있는 것이다. 우리는 실세계의 시스템을 모델링하고 있는데, 왜 비결정적인 기능을 포함시키려 하는가? 이에 대하여 여러 가지 답이 제시될 수 있다.

많은 결정적 알고리즘들은 어떤 단계에서 하나의 선택 또는 결정을 내리는 것을 필요로 한다. 그 대표적인 예가 게임 프로그램이다. 게임 프로그램의 각 단계에서 최적의 이동을 알 수 없는 경우가 빈번하게 나타나지만, 백트래킹 (backtracking) 등의 기법으로 모든 경우를 탐색해 봄으로써 이를 알아낼 수는 있다. 가능한 선택 대상이 여러 개 있는 경우 그 중의 하나를 선택하고 그 선택이 최적인지 아닌지가 명확히 밝혀질 때까지 검사를 계속한다. 선택이 최적이 아닐 경우, 마지막 결정 지점으로 되돌아와서 다른 선택에 대한 검사를 다시 시작하는 것이다. 최적의 선택을 할 수 있는 비결정적 알고리즘을 사용할 경우 백트래킹 없이 문제를 해결할 수 있으며, 결정적 알고리즘이 추가적인 작업을 통하여 비결정성을 시뮬레이션할 수 있다. 이러한 이유로 인하여 비결정적 기계는 탐색-백트랙 알고리즘 (search-and-backtrack algorithm) 에 대한 모델로 사용될 수 있다.

때로는 비결정성은 문제들을 쉽게 해결하는 데에 유용하다. 그림 8 의 nfa 를 살펴보자. 이 nfa 가 선택을 내려야 하는 곳은 분명하다. 하나의 선택을 할 경우 문자열 이 승인이 되며, 다른 선택을 할 경우 짝수 개의 a 를 갖는 모든 문자열들이 승인되게 된다. 따라서, 이 nfa 에 의해 인식되는 언어는 이다. 이 언어에 대한 dfa 를 구성할 수도 있지만, 이 경우 비결정성은 극히 자연스럽게 보인다. 이 언어는 제법 서로 다른 두 개 집합들의 합집합이며, 이 경우 비결정성은 시작에 필요한 결정을 할 수 있게 한다. 이 문제에 대한 결정적 해결법은 정의에서처럼 명확하지 않다. 앞으로도 비결정성이 유용함을 보이는 다른 예들을 더 보게 될 것이다.

같은 맥락으로, 비결정성은 몇몇 복잡한 언어들을 간명하게 정의하는 데에 효과적이다. 문법의 정의에서 비결정적 요소를 가지고 있음을 유의하라. 다음의 생성규칙을 보면,

모든 시점에 두 생성규칙들 중 하나를 선택하게 되어 있음을 알 수 있다. 이는 단지 두 개의 규칙으로 많은 문자열들을 지정할 수 있게 해준다.

마지막으로, 비결정성을 도입하는 데에는 기술적인 이유가 존재한다. 앞으로 보게 되겠지만, dfa 보다는 nfa 를 사용하는 경우 어떤 결론의 도출이 더 쉬워지는 경우가 존재한다. 다음 절에서 보게 되겠지만, 이 두 가지 형태의 오토마타 사이에는 근본적인 차이가 존재하지 않는다. 결과적으로 비결정성을 사용하는 것이 결론의 일반성을 그대로 유지하면서 형식적인 논증을 간단히 하는 효과를 보이게 되는 것이다.

연습문제

1. 본 절에서 언급한 대로 전이 그래프에 라벨 w 를 갖는 보행이 존재할 경우 이에는 라벨 w 이면서 길이가 Λ + (1 + Λ) |w| 이하인 보행이 존재함을 구체적으로 증명하라.

2. 그림 8 의 nfa 에 의해 정의된 언어를 인식하는 dfa 를 구성하라.

3. 그림 9 에서, 을 구하라.

4. 그림 10 에서, 를 구하라.

5. 그림 9 의 nfa 에 대하여, 을 구하라.

6. 집합 을 인식하는 상태의 수가 5 개 이하인 nfa 를 설게하라.

7. 언어 를 인식하는 세 개의 상태를 갖는 nfa 를 구성하라.

8. 연습문제 7 에서 보인 오토마타를 상태의 수를 세 개 미만으로 재구성할 수 있는가?

9. (a) 다음의 언어를 인식하는 세 개의 상태를 갖는 nfa 를 구성하라.

    (b) (a) 에서 보인 오토마타를 상태의 수를 세 개 미만으로 재구성할 수 있는가?

10. 에 대해 4 개의 상태를 갖는 nfa 를 구성하라.

11. 문자열 00, 01001, 10010, 000, 0000 가운데 어느 것이 다음의 nfa 에 의해 인식되는가?

12. 그림 10 에서 보인 nfa 에 의해 인식되는 언어의 여집합은 무엇인가?

13. L 을 그림 8 의 nfa 에 의해 인식되는 언어라 하자. 를 인식하는 nfa 를 구성하라.

14. 연습문제 12 에서 보인 언어를 글로 간단히 기술해 보아라.

15. 언어 를 인식하는 nfa 를 이 오토마타의 전이 그래프에서 간선 하나만을 제거했을 때 그 결과 오토마타가 언어 {a} 를 인식하도록 구성하라.

16. 연습문제 15 가 dfa 를 사용하여 해결될 수 있는가? 그렇다면 dfa 를 구성하고, 그렇지 않다면 그 이유를 설명하라.

17. 정의 6 을 다음과 같이 변형하는 것을 고려해 보자. 여러 개의 초기 상태를 갖는 nfa 가 다음과 같은 5 원소 쌍으로 정의된다.

     여기서 는 초기 상태들의 집합이다. 이 오토마타에 의해 인식되는 언어는 다음과 같이 정의된다.

     이와 같이 여러 개의 초기상태들을 갖는 모든 nfa 들에 대해, 같은 언어를 인식하면서 하나의 초기 상태를 갖는 nfa 가 존재함을 보여라.

18. 연습문제 17 에서 조건 을 추가할 경우 결과에 미치는 어떤 영향이 있는가?

19. 정의 5 를 사용하여 다음을 증명하라. 임의의 nfa 에서, 모든 q ∈ Q 와 모든 에 대해, 다음이 성립한다.

20. 아래의 조건을 만족하는 nfa 를 불완전한 dfa (incomplete dfa) 라 부른다.

        (a) λ-전이를 가지고 있지 않고,

        (b) 모든 q ∈ Q 와 a ∈ Σ 에 대하여, δ(q, a) 는 많아야 한 개의 원소를 갖는다.

     위 조건을 만족하는 오토마타는 선택을 결정할 필요가 없기 때문에 그런 이름으로 불리는 것이 합당하다.
Σ = {a, b} 에 대해, 아래에 주어진 불완전한 dfa 를 표준 dfa 로 변환하라.

3. 결정적 유한 인식기와 비결정적 유한 인식기의 동치성

이제 dfa 와 nfa 에 대한 근본적인 의문을 생각해 보자. 어떤 점에서 dfa 와 nfa 가 다른가? 이 두 오토마타의 정의에 차이점이 있음은 명백하지만, 그것이 이들 간에 근본적인 차이점이 잇음을 의미하지는 않는다. 이 의문을 구체적으로 탐구해 보기 위해, 오토마타들간의 동치성 (equivalence) 이라는 개념을 도입해 보자.

앞에서도 언급했듯이, 일반적으로 주어진 언어를 인식하는 인식기들은 여러 개 있으며, 따라서, 어느 dfa 나 nfa 든지 많은 동치인 인식기들이 있을 수 있다.

 

그림 11

여러 부류의 오토마타들을 비교할 때에, 항상 제기되는 의문은 한 부류가 다른 부류보다 강력한지 (powerful) 에 대한 것이다. 강력하다는 것은 한 종류의 오토마타가 다른 종류의 오토마타에서 수행할 수 없는 어떤 일을 수행할 수 있음을 의미한다. 이 의문을 유한 인식기에 대하여 생각해 보자. dfa 는 본질적으로 nfa 의 한 제한된 종류이므로, dfa 에 의해 인식되는 모든 언어는 어떤 nfa 에 의해서도 인식될 수 있음이 분명하다. 하지만, 그 역은 그리 당연하지 않다. nfa 에 비결정성이라는 개념이 추가되었고, 따라서 nfa 에 의해 인식되면서 dfa 로는 인식할 수 없는 언어가 존재한다고 생각해 볼 수는 있을 것이다. 결론을 말하자면, 이는 그렇지 않음이 밝혀져 있다. 오토마타들 중 dfa 들의 부류와 nfa 들의 부류는 똑같은 능력 (equally powerful) 을 가지고 있다. 즉, nfa 에 의해 인식되는 모든 언어들에 대해 이를 인식하는 dfa 가 항상 존재한다.

이 결과는 그리 당연하지 않으며, 확실히 검증되어야 할 것이다. 이 책에서의 모든 논증과 같이, 이 논증도 구성적 (constructive) 이 될 것이다. 즉, 이는 우리가 실제로 임의의 nfa 를 동치인 dfa 로 변환하는 방법을 제시할 수 있음을 의미한다. 이 변환은 그리 이해하기 어렵지 않으며, 원칙이 명확하다면, 이 원칙에서부터 시작하여 엄밀한 논증을 제시할 수 있다. 이 변환에 대한 이론적 근거는 다음과 같다. nfa 가 문자열 w 를 읽은 후, 우리는 그 nfa 가 정확히 어느 상태에 있을지를 알 수는 없지만, 이 nfa 가 놓여질 수 있는 가능한 상태들의 집합 ( 이라 하자) 가운데 하나라는 것은 알 수 있다. 동치인 dfa 는 같은 문자열을 읽어들인 후 명확히 한 상태에 놓이게 된다. 이러한 두 상황을 어떻게 연관시킬 것인가? 이에 대한 해답을 위해 다음과 같은 기교를 사용한다. 문자열 w 를 읽은 후, 동등한 dfa 가 라벨이 인 상태에 놓이도록, dfa 의 각 상태의 라벨이 nfa 의 상태들의 집합이 되도록 각 상태에 라벨을 부여한다. |Q| 개 상태들의 집합에 대하여, 개의 부분집합들이 존재하므로, 대응되는 dfa 에는 유한 개의 상태들이 존재하게 된다.

이와 같은 변환 과정에서의 대부분의 작업은 nfa 에서 가능한 상태와 입력들 간의 대응을 찾아내는 분석을 통해 이루어진다. 이에 대한 형식적인 과정을 보기 전에 우선 간단한 예제를 가지고 설명해 보자.

그림 12

그림 13

이 증명에서의 논증 과정은 옳기는 하지만, 중요한 부분만을 보이는 간결한 형태로 제시되었다. 이 책에서는 이후에도 증명에서의 기본적인 아이디어를 강조하고, 세세한 부분들은 생략하는 형태로 서술할 것이며, 이러한 세세한 부분들에 대해서는 독자들 스스로 완성해 보기 바란다.

위 증명 과정이 지루하기는 하지만, 이는 매우 중요하다. 이 모든 과정들을 이해하기 위해 다른 예제를 하나 보도록 하자.

정리 2 에서 얻을 수 있는 중요한 결론은 nfa 에 의해 인식되는 모든 언어들이 정규언어라는 것이다.

연습문제

1. 정리 2 의 변환 과정을 사용하여 그림 10 에서 보인 nfa 를 dfa 로 변환하라. 더 간단한 답을 보다 직접 확인할 수 있는지도 알아보아라.

2. 2 절의 연습문제 11 의 nfa 를 동치인 dfa 로 변환하라.

3. 다음 nfa 를 동치인 dfa 로 변환하라.

4. 정리 2 의 증명 과정을 구체적인 부분까지 완성하라. 특히, 를 포함할 경우 역시 를 포함한다는 사실을 구체적으로 보여라.

5. 모든 nfa 에 대해, L(M) 의 여집합이 집합 과 같다는 것이 참인가? 그렇다면 이를 증명하고, 그렇지 않다면 이에 대한 반례 (counterexample) 를 제시하라.

6. 모든 nfa 에 대해, L(M) 의 여집합이 집합 과 같다는 것이 참인가? 그렇다면 이를 증명하고, 그렇지 않다면 이에 대한 반례를 제시하라.

7. 임의의 개수의 종료 상태를 갖는 모든 nfa 들에 대해 오직 하나만의 종료 상태를 갖는 동치인 nfa 가 존재함을 증명하라. 유사한 주장이 dfa 에도 적용될 수 있는가?

8. 집합 을 인식하는 λ-전이가 없고 하나의 종료 상태만을 갖는 nfa 를 구성하라.

9. L 이 λ 를 포함하지 않는 정규 언어라 하자. L 을 인식하면서 λ-전이가 없고 종료 상태를 하나만 갖는 nfa 가 존재함을 보여라.

10. 2 절의 연습문제 17 에서 보인 바와 비슷한 방법으로 여러 개의 초기 상태들을 갖는 dfa 를 정의한다. 이에 대해 초기 상태를 하나만 갖는 동치인 dfa 가 항상 존재하는가?

11. 모든 유한언어들이 정규 언어임을 증명하라.

12. L 이 정규언어이면, 역시 정규 언어임을 증명하라.

13. 그림 16 의 dfa 에 의해 인식되는 언어를 말로 간단히 설명하라. 이를 이용하여, 주어진 dfa 와 동치이면서 더 적은 수의 상태들을 갖는 다른 dfa 를 구성하라.

14. L 을 임의의 언어라 하자. 임의 문자열 w 에서 짝수 위치에 있는 문자들을 추출하여 얻어진 문자열을 even(w) 라 정의한다 ; 즉,

     인 경우, even(w) 는 다음과 같다.

     이에 대응하여, 다음과 같이 새로운 언어를 정의할 수 있다.

     L 이 정규 언어이면, even(L) 도 정규 언어임을 증명하라.

15. 주어진 언어 L 에 대해, L 에 속한 모든 문자열의 가장 왼쪽 두 심볼을 제거하여 얻어진 새 언어를 chop2(L) 라 한다. 즉,

     L 이 정규 언어이면, chop2(L) 도 정규 언어임을 증명하라.

4. 유한 오토마타에서의 상태의 수 축소

어느 dfa 나 유일하게 하나의 언어를 정의하게 된다. 하지만, 그 역은 성립하지 않는다. 즉, 주어진 하나의 언어에 대해 이를 인식하는 dfa 는 여러 개가 존재할 수 있는 것이다. 서로 동치인 오토마타들에 대해서도 이들의 상태의 수는 적지 않은 차이가 난다. 지금까지 고려해 온 의문에 의하면, 기능상 정확하기만 하다면 어떤 오토마타가 구성되든 관계가 없었으나, 그 결과를 현실세계에 실제로 사용하려 한다면, 다른 것보다 특정 dfa 를 선호해야 하는 이유가 존재하게 된다.

전적으로 이론적인 관점에서만 본다면, 그림 17(a) 의 오토마타에 비해 그림 17(b) 의 오토마타를 선호해야 할 이유는 거의 없다. 하지만, 단순성을 고려할 때 두 번째 오토마타가 명백히 더 좋아 보인다. 계산을 목적으로 오토마타를 표현하고자 할 때 상태의 수에 비례하여 기억 공간이 필요하게 된다. 공간 효율성을 고려한다면 오토마타의 상태의 수를 가급적 줄이는 것이 바람직할 것이다. 이제 이를 위한 알고리즘을 소개하고자 한다.

그림 17

분명히 두 개의 상태는 구분불가능이거나 구분가능이 될 것이다. 구분불가능성은 동치 관계의 성질을 갖는다 : 상태 p 와 q 가 구분불가능이고, 상태 q 와 r 이 또한 구분불가능성이면, 상태 p 와 r 도 구분불가능이며, 결국 세 상태 모두 구분불가능이다.

임의의 dfa 에서 상태의 수를 줄이는 한 가지 방법은 구분불가능 상태들을 찾아내어 이들을 병합하는 것이다. 우선 구분가능한 상태들의 쌍을 찾아내는 방법을 설명한다.

이 프로시저가 모든 구분가능한 쌍들을 마크하는 알고리즘이 된다.

프로시저 mark 가 실행된 후에, 이 결과를 이용하여 dfa 의 상태 집합 Q 를 서로 소인 부분집합들, 로 분할 (partition) 한다. 이 분할에서 각 상태 q ∈ Q 는 이 부분집합들 중 하나에만 속해야 하며, 한 부분집합에 속한 상태들은 서로 구분불가능해야 하고, 서로 다른 부분집합에 속한 상태들은 서로 구분가능해야 한다. 본 절의 연습문제 11 에서 대략 설명된 결과를 이용하여, 이러한 분할이 항상 찾아질 수 있음을 증명할 수 있다. 이와 같이 구성된 부분집합들을 이용하여 다음 프로시저에 따라 최소 수의 상태들을 갖는 오토마타를 구성할 수 있다.

그림 18

그림 19

연습문제

1. 그림 16 의 dfa 의 상태의 수를 최소화하라.

2. 다음 언어들에 대한 최소 dfa 를 구성하라. 각 경우에 대한 결과가 최소임을 증명하라.

        (a)

        (b)

        (c)

        (d)

3. 프로시저 reduce 에 의해 구성되는 오토마타가 결정적 오토마타임을 보여라.

4. 다음 다이어그램에서 보인 dfa 의 상태의 수를 최소화하라.

5. L 은 공집합이 아닌 언어로서 L 에 속한 문자열 w 는 길이가 n 이상이라 할 때, L 을 인식하는 dfa 의 상태의 수가 적어도 n + 1 이상임을 보여라.

6. 다음 주장에 대해 맞으면 이를 증명하고 틀리면 그 주장이 틀림을 증명하라. 이 정규 언어 L 을 인식하는 최소 dfa 라면, 을 인식하는 최소 dfa 가 된다.

7. 구분불가능성 (indistinguishability) 은 동치 관계이지만, 구분가능성 (distinguishability) 은 동치 관계가 아님을 보여라.

8. 이 원래의 dfa 와 동치라는, 정리 4 의 첫 부분의 제안된 증명의 정확한 단계들을 보여라.

9. 임의의 주어진 dfa 에 대해 최소 dfa 를 생성하는 컴퓨터 프로그램을 작성하라.

10. 다음을 증명하라. 상태 가 구분불가능이고, 상태 가 구분가능일 때, 상태 가 구분가능이 됨을 증명하라.

11. 프로시저 mark 가 실행이 완료된 후 수행되는 다음 과정을 생각해 보자. 어떤 상태 에서 시작한다. 와 구분가능하다고 마크된 모든 상태들을 의 동치 집합 (equivalence set) 에 포함시키고, 다음으로 이 집합에 포함되지 않은 다른 상태에 대해 같은 과정을 반복한다. 이 과정을 더 이상의 상태가 남지 않을 때까지 계속한다. 이 과정을 알고리즘으로 명확하게 기술하고, 이 알고리즘이 원래의 상태들의 집합을 동치 집합들로 분할함을 증명하라.