유한 오토마타

형식 언어와 오토마타 : 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) 유한 인식기와 전이 그래프

 정의 1

결정적 유한 인식기 (deterministic finite accepter 혹은 dfa) M 은 다음과 같은 5원소 쌍 (quintuple) 으로 정의된다.

M = (Q, Σ, δ, q₀, F)

여기서 각 구성요소들은 다음의 의미를 갖는다.

Q 는 내부 상태 (internal state) 들의 유한 집합이다.
Σ 는 문자들의 유한 집합이며, 입력 알파벳 (input alphabet) 으로 불린다.
δ : Q × Σ → Q 는 전체 함수(total function)이며, 전이 함수 (transition function) 라 불린다.
q₀ ∈ Q 는 초기 상태 (initial state) 를 의미한다.
F ⊆ Q 는 종료 상태 (final state) 들의 집합을 의미한다.

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

δ(q₀, a) = q₁

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

그림 1

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

 예제 1

그림 1의 그래프는 다음과 같은 dfa 를 표현한다.

M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {q₁})

여기서 전이 함수 δ는 다음과 같이 주어진다.

δ(q₀, 0) = q₀,            δ(q₀, 1) = q₁
δ(q₁, 0) = q₀,            δ(q₁, 1) = q₂
δ(q₂, 0) = q₂,            δ(q₂, 1) = q₁ 

이 dfa 는 문자열 01 을 승인한다. 상태 q₀에서 시작하여, 먼저 심볼 0이 읽혀진다. 이때 그래프의 간선들을 살펴보면, 오토마타는 상태 q₀ 에 남게 됨을 알 수 있다. 다음으로 1 이 읽혀지고 오토마타의 상태는 q₁ 으로 전이된다. 이제 오토마타는 문자열의 끝에 놓이고, 동시에 종료 상태에 있게 되므로 문자열 01이 승인된다. 이 dfa 가 문자열 00 은 인식하지 못한다. 그 이유는 두 개의 0 을 읽은 후에 오토마타는 상태 q₀ 에 있게 되며 이는 종료 상태가 아니기 때문이다. 비슷한 이유로, 이 오토마타가 문자열 101, 0111, 11001 등을 승인하지만, 100, 1100 등은 승인하지 못함을 알 수 있다.

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

이고

이면, 다음이 성립한다.

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

                                                                                        (1)

                                                                         (2)

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

                                                                         (3)

그리고 다음을 얻는다.

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

(2) 언어와 Dfa

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

 정의 2

dfa 에 의해 인식되는 언어란 M 에 의해 승인되는 Σ 에 대한 모든 문자열들의 집합이다. 형식적인 표현을 사용하면, 다음과 같다.

전이 함수 δ 와 확장 전이 함수 가 모두 전체 함수임을 유의하여야 한다. 각 단계에서, 단 하나의 전이만이 정의되며, 따라서 우리는 이 오토마타를 결정적 (deterministic) 이라 한다. dfa 는 의 모든 문자열들을 처리하여 이를 승인하거나 승인하지 않는다. 승인하지 않는다는 것은 주어진 dfa 가 종료 상태가 아닌 다른 상태에서 종료함을 의미하며, 따라서 다음이 성립한다.

 예제 2

그림 2 의 dfa 를 생각해 보자.

그림 2 에서는 하나의 간선에 두 개의 라벨을 지정하고 있다. 이와 같이 여러 개의 라벨을 갖는 간선은 둘 이상의 서로 다른 전이들을 간략히 표현한 것이며, 입력 문자가 간선 라벨들 가운데 어느 것과 일치하더라도 전이가 발생하게 됨을 의미한다.

그림 2 의 오토마타는 b 를 만날 때까지 초기 상태 에 남아 있는다. b 를 읽으면 상태 으로 전이한다. 이때 읽은 b 가 마지막 심볼인 경우 입력 문자열은 승인된다. 그렇지 않은 경우에는, 상태 로 전이하고 이후 그 상태를 벗어날 수 없게 된다. 이러한 상태를 트랩 상태 (trap state) 라 한다. 주어진 그래프를 보면 이 오토마타가 임의의 개수의 a 와 그 뒤에 마지막으로 b 를 갖는 문자열들만을 모두 승인하며, 나머지 문자열들은 모두 거부됨을 알 수 있다. 집합 표현으로 하면, 이 오토마타에 의해 인식되는 언어는 다음과 같다.

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

그림 2

 정리 1

을 결정적 유한 인식기라 하고, 이 이에 관련된 전이 그래프라 하자. 모든 와 에 대해, 이고 오직 그럴 때에만 그래프 에는 라벨 w 를 갖는 부터 까지의 보행이 존재한다.

증명 : 이는 예제 1 의 간단한 경우에서 보았듯이 자명한 사실이며, 문자열 w 의 길이에 대해 귀납법으로 엄격하게 증명할 수 있다. 위 정리가 길이가 n 이하인 모든 문자열 v 에 대해 참이라고 가정하자. 길이가 n + 1 인 문자열 w 를 생각해 보자. w 는 다음과 같이 표현될 수 있다.

w = va

라고 가정해 보자. 그러면 |v| = n 이므로 에는 라벨 v 를 갖는 부터 까지의 보행이 존재하여야 한다. 이때 라면 오토마타 M 은 전이 를 가져야 하며, 따라서 은 라벨 a 를 갖는 간선 를 갖게 된다. 결국, 에는 와 사이에 라벨 va = w 를 갖는 보행이 존재한다. 이 결과는 n = 1 일 때 명확히 성립하므로, 귀납법에 따라 모든 에 대해,

                                                                          (4)

라는 사실이 에 라벨 w 를 갖는 로부터 까지의 보행이 존재한다는 것을 의미한다.

간단하게 이의 역, 즉 이러한 경로가 존재하면 식 (4) 가 성립함을 의미한다는 것도 증명할 수 있으며, 이로써 증명이 완성된다.

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

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

그림 3

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

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

 예제 3

알파벳 Σ = {a, b} 에 대한 문자열들 중 ab 로 시작하는 모든 문자열들을 인식하는 결정적 유한 인식기를 구성해 보자.

여기서는 입력되는 문자열의 처음 두 심볼이 중요하다. 이 두 심볼이 입력된 이후에는 더 이상 어떤 결정을 내릴 필요가 없다. 따라서 우리는 이 문제를 4 개의 상태, 즉, 초기 상태와 ab 를 인식하기 위한 두 개의 상태 (이 두 상태들 중 마지막 상태는 종료 상태이자 트랩 상태가 된다), 그리고 종료 상태가 아닌 트랩 상태를 갖는 오토마타로 해결할 수 있다. 입력의 첫 심볼이 a 이고 두 번째 심볼이 b 이면 이 오토마타는 종료 트랩 상태 (final trap state) 로 전이하며, 이후의 입력에 관계없이 이 상태에 남게 된다. 반면에, 첫 심볼이 a 가 아니거나 두 번째 심볼이 b 가 아닌 경우에는 오토마타가 비종료 트랩 상태 (nonfinal trap state) 로 전이된다. 이의 전이 그래프는 그림 4 에서 보여진다.

그림 4

 예제 4

{0, 1} 에 대한 문자열들 가운데 부문자열 001 을 포함하는 문자열을 제외한 모든 문자열을 승인하는 dfa 를 구성해 보자.

부문자열 001 이 나타나는지를 확인하기 위해서는 현재의 입력 문자뿐만 아니라 그 직전에 두 개의 0 이 선행되었는지를 기억해야 하며, 이는 오토마타에 특별한 상태들을 두고 이에 라벨을 적절하게 부여함으로써 해결할 수 있다. 프로그래밍 언어에서 변수에 이름을 부여하듯이 오토마타에서의 상태 이름도 임의로 주어지며 기억에 도움이 되는 이름을 선택할 수 있다. 예를 들어, 두 개의 0 이 직전에 읽혀진 경우 그 상태에 00 이라는 라벨을 부여할 수 있다.

입력 문자열이 001 로 시작하는 경우 이 문자열은 거부된다. 이는 초기 상태에서 비종료 상태로 라벨 001 을 갖는 경로가 있어야 함을 의미한다. 편리를 위해 이 비종료 상태에 001 이라는 라벨을 부여한다. 이후의 입력 문자열로 무엇이 입력되든 이 문자열은 거부되어야 하므로 이 상태는 반드시 트랩 상태이어야 한다. 다른 모든 상태들은 종료 상태가 된다.

이와 같이 함으로써 구성하고자 하는 오토마타의 구조에 대한 기본적인 윤곽이 형성되지만, 우리는 입력 문자열의 중간에 001 이 나타나는 경우에 대해서도 고려하여야 한다. 입력 문자열을 승인할 것인가 아니면 거부할 것인가에 대해 정확한 결정을 하기 위해서 필요한 사항들이 오토마타에 의해 기억될 수 있도록 Q 와 δ 를 정의하여야 한다. 이 경우에, 하나의 심볼이 읽혀졌을 때 그 직전, 즉 왼쪽의 부문자열에 대한 정보가 필요하다. 예를 들어, 직전의 두 심볼이 00 인지를 확인할 수 있어야 한다. 상태에 관련된 심볼들을 라벨로 부여할 경우, 어떤 전이들이 있어야 하는지에 대해 쉽게 알 수 있게 된다. 예를 들어, 다음을 알 수 있다.

δ(00, 0) = 00

이는 연속으로 세 개의 0 이 있는 경우에 나타나는 상황이다. 우리는 마지막 두 심볼에 대해서만 알 필요가 있으며, 결과적으로 dfa 가 상태에 유지하여 기억할 상실은 00 이다. 완전한 해, 즉 완성된 dfa 가 그림 5 에서 보여진다. 이 예제에서 상태에 기억에 도움이 되는 라벨을 부여하는 것이 작업의 진행을 확인하는 데 얼마나 도움이 되는가를 알 수 있을 것이다. 위의 해답이 정확한지를 확인하기 위하여 문자열 100100, 1010100 등을 입력 문자열로 하여 위 오토마타를 검사해 보라.

그림 5

(3) 정규 언어

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

 정의 3

언어 L 에 대하여, L = L(M) 을 만족하는 결정적 유한 인식기 M 이 존재하고 오직 그럴 때에만 L 을 정규 언어 (regular language) 라 부른다.

 예제 5

다음 언어 L 이 정규 언어임을 보여라.

L = {awa : w ∈ {a, b}^*}

이 언어 L 을 포함하여 임의의 언어가 정규 언어임을 보이기 위해서, 그 언어에 대한 dfa 를 찾아야 한다. L 에 대한 dfa 는 조금 더 복잡하기는 하다. 이 dfa 가 해야 하는 일은 입력 문자열이 a 로 시작하고 a 로 끝나는가를 검사하는 것이며 그 사이에 어떤 문자열이 있더라도 상관없다. 입력 문자열의 끝에 대한 검사를 하기 위한 명확한 방법이 없기 때문에 이 문제의 해는 복잡해진다. 하지만, 이 어려움은 또 다른 a 가 읽혀질 때마다 dfa 를 종료 상태에 놓이게 함으로써 해결될 수 있다. 만약 이 심볼이 마지막이 아니고, b 가 읽혀지면, dfa 로 하여금 종료 상태에서 다시 벗어나게 한다. 이와 같이 입력 심볼들을 처리하면서, 그 이후에 다시 a 가 읽혀질 때마다 오토마타는 다시 종료 상태에 놓이게 된다. 완전한 dfa 가 그림 1 에서 주어진다. 이 오토마타가 정상적으로 작동하는지를 보기 위해 몇 가지 입력 예들을 가지고 검사해 보아라. 한두 번의 검사 후에는 이 dfa 가 입력 문자열이 a 로 시작하고 a 로 끝나고 오직 그럴 때에만 승인한다는 사실이 명확해질 것이다. 주어진 언어에 대한 dfa 가 구성되었으므로 정의에 따라, 이 언어가 정규 언어임을 알 수 있다.

 예제 6

L 을 예제 5 에서 주어진 언어라 하자. L² 이 정규 언어임을 보여라. 이전과 마찬가지로 이 언어가 정규 언어임을 보이기 위해서는 이 언어에 대한 dfa 를 구성해 보면 될 것이다. 언어 L² 을 명확하게 표현하면 다음과 같다.

L² = {aw₁aaw₂a : w₁, w₂ ∈ {a, b}^*}

따라서, 이 언어를 인식하는 dfa 를 구성하기 위해서는 같은 형태를 갖는 두 개의 연속된 문자열을 인식하는 dfa 가 필요하다(물론, 이 두 개의 연속된 문자열이 완전히 같은 문자열일 필요는 없다). 이를 위해서 그림 6 에서 보인 dfa 가 기본 구조로 사용될 수 있다. 그러나 정점 q₃ 는 수정되어야 한다. 상태 q₃ 에 도달하면 우리는 이 시점에서 두 번째 문자열이 awa 의 형태를 갖는지를 검사해야 하기 때문에, q₃ 는 더 이상 종료 상태일 수가 없다. 이와 같이 두 번째 문자열을 인식하기 위해서는, dfa 의 상태들을(물론, 새 이름으로) 복제하고, 상태 q₃ 를 두 번째 부분의 시작 정점으로 한다. 전체 입력 문자열은 aa 가 나타나는 지점에서 두 부분으로 분리될 수 있으므로, aa 가 처음 나타나는 지점에서 오토마타를 두 번째 부분으로 진입하도록 한다. 이는 전이가 δ(q₃, a) = q₄ 가 되도록 함으로써 가능해진다. 완전한 dfa 를 그림 7 에 나타내었다. 이 dfa 가 L² 을 인식함을 확인할 수 있고, 따라서 이 언어는 정규 언어이다.

그림 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) 으로 갖게 함으로써 가능해진다.

 정의 4

비결정적 유한 인식기(nondeterministic finite accepter) 또는 nfa 는 다음과 같은 5 원소 쌍으로 정의된다.

M = (Q, Σ, δ, q₀, F)

여기서 Q, Σ, q₀, F 는 결정적 유한 인식기에서와 같이 정의되고, 그러나 전이 함수 δ 는 다음과 같다.

δ : Q × (Σ ∪ {λ}) → 2^Q

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

δ(q₁, a) = {q₀, q₂}

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

 예제 7

그림 8 에 있는 전이 그래프를 고려해 보자. 이는 로부터의 라벨 a 를 갖는 전이가 두 개 있으므로, 비결정적 인식기를 나타낸다.

그림 8

그림 9

 예제 8

한 비결정적 오토마타가 그림 9 에서 보여진다. 이 오토마타는 하나의 정점으로부터 같은 라벨을 갖는 여러 개의 간선들이 있을 뿐 아니라, 또한 λ-전이를 가지므로 비결정적이다. δ(q₂, 0) 와 같은 몇몇 전이는 그래프에 명시되어 있지 않다. 이는 공집합으로의 전이로 해석된다. 즉, δ(q₂, 0) = Ø 이다. 이 오토마타는 λ, 1010, 101010 등의 문자열들을 승인하지만, 110, 10100 등은 승인하지 못한다. 입력 10에 대해서 두 가지 다른 보행이 가능하다. 하나는 q₀ 에 도달하고, 다른 하나는 q₂ 에 도달한다. q₂ 는 종료 상태가 아니지만, 이 문자열은 종료 상태에 도달하는 보행을 가지므로 승인된다.
dfa 에서와 마찬가지로 nfa 에서도 전이 함수는 두 번째 인수로 문자열을 갖도록 확장될 수 있다. 확장 전이 함수 δ^* 는 다음의 성질을 만족해야 한다. 만일

δ^*(q_i, w) = Q_j

인 경우, 오토마타가 상태 q_i 에서 시작하여 입력 문자열 w 을 읽은 후에 놓여질 수 있는 상태들의 집합이 Q_j 이다. 확장 전이 함수 δ^* 를, 식 (1) 과 (2) 와 유사하게, 순환적으로 정의하는 것이 가능하지만, 그 정의가 그리 명백하지 않다. 그보다 더 이해하기 쉬운 정의를 전이 그래프를 이용하여 내릴 수 있다.

 정의 5

nfa 의 확장 전이 함수는 다음과 같이 정의된다. 전이 그래프에서 로부터 로의 라벨 w 를 갖는 보행이 존재하고 오직 그럴 때에만 가 를 포함한다. 이는 모든 와 에 대해 성립한다.

그림 10

 예제 9

그림 10 은 하나의 nfa 를 보여주고 있다. 이 nfa 에는 여러 개의 λ-전이가 존재하며, 또한 와 같이 정의되지 않은 전이들도 존재한다.

여기서 와 를 구해 보자. 이 nfa 에는 에서 라벨 a 를 갖는 간선과 두 개의 λ-간선을 거쳐 자신에게로 돌아가는 보행이 존재한다. 또한, 에서 λ-간선들을 거쳐 와 로 가는 보행도 존재한다. 따라서, 다음이 성립한다.

와 사이에 λ-간선이 존재하므로, 가 를 포함하는 것을 알 수 있다. 또한, 모든 상태는 이동 없이, 즉 입력 심볼 없이, 자신에게 도달할 수 있으므로 는 도 포함한다.

따라서 다음이 성립한다.

λ-전이를 필요한 만큼 사용하면, 다음이 성립함도 알 수 있을 것이다.

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

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

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

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

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

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

 정의 6

nfa 에 의해 인식되는 언어는 위에서 설명한 방식으로 승인되는 문자열들의 집합으로 정의된다. 이를 형식적으로 정의하면 다음과 같다.

즉, 이 언어는 전이 그래프의 초기 정점에서 종료 정점까지 라벨이 w 인 보행이 존재하는 모든 문자열 w 들로 구성된다.

 예제 10

그림 9 의 오토마타에 의해 인식되는 언어가 무엇인지에 대해 알아보자. 그래프를 보면, 이 nfa 가 종료 상태에 도달할 수 있는 방법은 오직 입력 문자열이 10 의 반복으로 이루어지는 경우와 빈 문자열인 경우임을 쉽게 알 수 있다. 따라서 이 오토마타는 언어 을 인식한다.

문자열 w = 110 이 입력되는 경우 이 오토마타에는 어떤 일이 발생하겠는가? 우선 문자열 11 을 받아들인 뒤에 오토마타는 상태 에 있게 되는데, 이 상태에서 전이 는 정의되어 있지 않다. 이러한 상황을 종말 형상 (dead configuration) 이라 하며, 이때 오토마타는 더 이상의 움직임이 없이 정지한다고 생각할 수 있다. 하지만, 이러한 해석은 정확한 것이 아니며 어느 정도 오해의 위험을 안고 있음을 명심하여야 한다. 다만, 명확하게 언급할 수 있는 사실은 다음과 같다.

따라서, 입력 문자열 w = 110 으로는 종료 상태에 도달될 수 없으며, 따라서 이 문자열은 승인되지 않는다.

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

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

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

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

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

S → aSb | λ

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

마지막으로, 비결정성을 도입하는 데에는 기술적인 이유가 존재한다. 앞으로 보게 되겠지만, 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 원소 쌍으로 정의된다.

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

        L(M) = {w : 임의의 에 대해, 는 를 포함한다}

     이와 같이 여러 개의 초기상태들을 갖는 모든 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) 이라는 개념을 도입해 보자.

 정의 7

다음과 같이 조건이 만족되는 경우,



즉, 두 오토마타가 같은 언어를 인식하는 경우, 두 개의 유한 인식기 과 는 동치라 한다.

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

 예제 11

그림 11 의 dfa 는 그림 9 의 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

그림 12 의 nfa 를 동치인 dfa 로 변환해 보자. 이 nfa 는 상태 에서 시작하며, 따라서 dfa 의 초기 상태에 라벨 를 부여한다. 문자 a 를 읽은 후, 이 nfa 는 상태 에 놓이거나 또는 λ-전이를 한 후 상태 에 놓이게 된다. 따라서, 해당 dfa 는 라벨이 인 상태와 다음과 같은 전이를 가져야 한다.

상태 에서는, 심볼 b 가 입력되었을 때 nfa 의 상태 전이는 정의되어 있지 않으며, 따라서 해당 dfa 는 다음의 전이를 가져야 한다.

라벨 Ø 을 갖는 상태는 nfa 에 대한 불가능한 이동을 표현하는 것이며, 따라서, 문자열을 승인할 수 없음을 의미한다. 결국 dfa 에서의 이 상태는 비종료 트랩 상태여야 한다.

이제 dfa 에 상태 가 추가되었으며, 따라서 이 상태로부터 다른 상태로의 전이도 생각해야 한다. dfa 에서의 이 상태는 nfa 에서의 두 개의 상태에 해당함을 상기하고, 따라서 nfa 를 다시 참조하여야 한다. 이 nfa 가 상태 에 있고 a 를 읽을 경우에는 그대로 상태 에 놓이게 된다. 또한, 이 nfa 는 상태 에서 λ-전이를 통해 상태 로 전이할 수 있다. 같은 입력에 대해, 이 nfa 는 상태 에서 어떤 전이도 정의되어 있지 않다. 따라서 다음을 알 수 있다.

유사하게, 다음의 결과도 알 수 있다.

이제, 각 상태에 대해 모든 전이가 정의되었다. 그 결과 주어진 nfa 와 동치인 dfa 를 구성할 수 있으며, 이는 그림 13 에서 보여진다. 그림 12 의 nfa 는 가 을 포함하는 모든 문자열 w 를 승인한다. 이에 대응하는 dfa 에서 이러한 문자열들을 모두 승인하기 위해서는 주어진 라벨에 을 포함하는 모든 상태들이 종료 상태가 되도록 하여야 한다.

그림 12

그림 13

 정리 2

언어 L 을 비결정적 유한 인식기 에 의해 인식되는 언어라 하자. 이 때 다음을 만족하는 결정적 유한 인식기 가 항상 존재한다.

증명 : 주어진 에 대해, 이와 동치인 에 대한 전이 그래프 를 구성하기 위하여 아래에 주어진 프로시저 nfa_to_dfa 를 사용한다. 이 과정을 이해하기 위해서 가 몇 가지 특정 성질들을 가져야 함을 기억하자. 이 그래프에서 모든 정점들은 정확히 |Σ| 개의 진출 간선 (outgoing edge) 들을 가져야 하며, 이때 각 간선들은 Σ 의 서로 다른 원소들을 라벨로 가져야 한다. 이 변환 과정의 중간에 몇몇 간선들이 누락될 수도 있지만, 이 프로시저는 모든 간선들이 주어질 때까지 계속 진행될 것이다.

procedure : nfa_to_dfa

1. 정점 를 갖는 그래프 를 생성한다. 이 정점을 초기 정점으로 한다.

2. 다음 과정을 모든 간선들이 생성될 때까지 반복한다.
   Σ 의 어떤 원소 a ∈ Σ 에 대해 진출 간선을 갖지 않는 의 정점 를 선택한다.
    들을 계산한다.
   계산된 들의 합집합을 구하여 이를 이라 한다.
    에 라벨이 인 정점이 이미 존재하지 않았다면 이를 추가한다.
    에 정점 로부터 정점 으로 향하는 간선을 추가하고 이에 라벨 a 를 부여한다.

3. 의 상태들 중 라벨이 을 포함하는 모든 상태들을 종료 상태로 지정한다.

4. 인식기 이 λ 를 인식하는 경우, 의 정점 를 종료 정점으로 지정한다.

이 프로시저가 항상 종료함은 명백하다. 단계 2 의 루프가 수행될 때마다 에 간선이 하나씩 추가된다. 의 간선의 개수가 많아야 개이므로 이 루프는 유한 시간내에 종료하게 된다. 이 변환 과정이 정확한 해답을 생성함을 보이기 위해, 입력 문자열의 길이에 대해 귀납법으로 이를 증명한다.

길이가 n 이하인 모든 문자열 v 에 대해 그래프 에 정점 에서 정점 로 가는 라벨이 v 인 보행이 존재함은 에 에서 한 상태 로 가는 라벨이 v 인 보행이 존재함을 의미한다고 가정하자. 이제 문자열 w = va 에 대해 에서 에서 로 가는 라벨이 w 인 보행을 생각해 보자. 이 경우 에서 로 가는 라벨이 v 인 보행과 에서 로 가는 간선 (또는 간선들의 순서열) 이 존재한다. 귀납 가정에 따라 에는 에서 로 가는 라벨이 v 인 보행이 존재할 것이다. 또한 위 프로시저의 변환 과정에 따라 이에는 로부터 라벨이 을 포함하는 어떤 상태로의 보행이 존재할 것이다. 따라서 위 귀납 가정은 길이가 n + 1 인 모든 문자열들에 대해 성립한다. 이는 n = 1 인 경우 명백히 만족되므로 모든 n 에 대해 만족된다. 결과적으로 이 종료 상태 를 포함하는 경우 역시 그러하다. 이 증명을 완성하기 위해서는, 역으로 이 를 포함할 경우 역시 그러하다는 것을 보이면 된다.

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

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

 예제 13

그림 14 의 nfa 를 동치인 dfa 로 변환해 보도록 하자. 여기서 이므로 의 상태 을 생성하고, 로부터 으로의 라벨 0 인 간선을 추가한다. 같은 방법으로, 이므로, 에 상태 을 생성하고 로부터 으로의 라벨 1 인 간선을 추가한다.

아직 모든 간선들이 생성되지 않았으므로, 정리 2 의 변환 과정을 사용하여 계속한다. 이 변환 과정에서 a = 0, I = 0, j = 1 을 가지고 다음을 계산한다.



그림 14



그림 15



그림 16

이에 따라 새로운 상태 와 다음 전이가 추가된다.

다음으로, a = 1, i = 0, j = 1, k = 2 를 사용하면, 다음을 알 수 있으며,

이에 따라 또 다른 상태 를 추가한다. 이제 우리는 그림 15 에서 보여진 오토마타를 부분적으로 구성하여 보았다. 아직도 완성되지 않은 간선들이 존재하므로, 그림 16 에서 보인 완전한 dfa 가 얻어질 때까지 이 구성 과정은 계속되어야 한다.

정리 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) 는 다음과 같다.

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

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

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

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

chop2(L) = {w : vw ∈ L, |v| = 2}.

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

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

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

 예제 14

그림 17(a) 와 (b) 에서 보인 두 개의 dfa 는 동치이며, 이는 몇 개의 문자열들만 검사해 보아도 쉽게 알 수 있다. 이 중 그림 17(a) 의 dfa 에는 몇 가지 명백하게 불필요한 특징들이 존재한다. 우선, 상태 는 초기 상태 에서 도달할 수 없는 상태이기 때문에 이 오토마타에서 아무런 역할도 하지 못한다. 이러한 상태는 도달불가능 상태이며, 오토마타가 인식하는 언어에 아무런 영향을 주지 않고 관련된 간선들과 함께 제거될 수 있다. 이 상태 를 제거한다고 하더라도 이 오토마타에는 필요없는 부분이 계속 존재한다. 첫번째 이동 이후에도 도달가능한 상태들이 이후에 도달가능한 상태들과 그 형상이 같다. 그림 17(b) 의 오토마타는 이 두 관찰을 반영하여 합성한 결과이다.

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

 정의 8

임의의 dfa 에서의 두 상태 p 와 q 에 대해, 이들이 모든 문자열 에 대해 다음 조건을 만족하는 경우 이들을 구분불가능 (indistinguishable) 이라 한다.

그림 17

는 를 의미한다.

그리고

는 를 의미한다.

한편, 다음 조건을 만족하는 문자열 가 존재하는 경우, 상태 p 와 q 는 문자열 w 에 의해 구분가능 (distinguishable) 이라 한다.

는

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

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

procedure : mark

1. 모든 도달불가능 상태들을 제거한다. 이는 dfa 의 그래프에서 초기 상태로부터의 모든 단순 경로들을 열거함으로써 수행될 수 있다. 이러한 경로상에 나타나지 않는 상태들은 도달불가능한 것이다.

2. 상태들의 모든 쌍 (p, q) 에 대해 p ∈ F 이고 이거나 이고 q ∈ F 인 경우에는 (p, q) 를 구분가능이라 마크한다.

3. 이전에 마크되지 않은 상태 쌍이 더 이상 마크되지 않을 때까지 다음 작업을 계속한다.

모든 쌍 (p, q) 와 모든 a ∈ Σ 에 대해, 와 를 계산한다. 이때 쌍이 구분가능으로 마크되어 있으면, (p, q) 를 구분가능으로 마크한다.

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

 정리 3

프로시저 mark 는, 어느 dfa 에 적용되든지, 유한 시간 내에 종료하며, 모든 구분가능한 쌍들을 검출한다.

증명 : 어떤 dfa 에도 마크될 수 있는 상태 쌍의 개수는 유한하므로, 위 프로시저는 명백히 유한 시간내에 종료된다. 또한, 이 프로시저에 의해 마크된 쌍들이 모두 구분가능함도 쉽게 알 수 있다. 증명이 필요한 부분은 위 프로시저가 모든 구분가능한 쌍들을 검출하는가에 대한 사항이다.

우선, 상태 와 가 길이 n 인 문자열에 의해 구분가능하기 위한 필요충분 조건은 어떤 a ∈ Σ 에 대해 다음과 같은 전이가 존재하고,

                                                                           (5)

                                                                           (6)

이때, 와 이 길이가 n - 1 인 문자열들에 의해 구분가능해야 한다. 우리는 이를 이용하여 프로시저 mark 에서 단계 3 의 루프를 n 번째 통과할 때 길이가 n 이하인 문자열들에 의해 구분가능한 모든 상태들이 마크됨을 보일 수 있다. 프로시저 mark 의 단계 2 에서는 λ 에 의해 구분가능한 모든 쌍들이 마크되며, 따라서 이에 대한 귀납적 증명을 위한 n = 0 인 경우의 기저 단계가 성립된다. 이제 이 사실이 i = 0, 1, ..., n - 1 인 경우에 참이라 가정하자. 이 가정에 따라 위 프로시저의 루프를 n 번째 통과하기 직전에 길이 n - 1 인 모든 문자열들에 의해 구분가능한 상태들은 마크된다. 식 (5) 와 (6) 에 의해 프로시저의 루프를 n 번째까지 완료한 이후에는 길이 n 이하인 문자열들에 의해 구분가능한 모든 상태들이 마크될 것이다. 따라서, 귀납법에 의하여, 모든 n 에 대해, 위 프로시저가 루프를 n 번째까지 완료한 이후에는, 길이 n 이하인 모든 문자열들에 의해 구분가능한 모든 상태들이 마크되어 있게 된다.

이 프로시저가 모든 구분가능한 상태들을 마크한다는 것을 보이기 위해, 이 루프가 n 번 반복 후에 종료한다고 가정하자. 이는 루프를 n 번째 수행하는 과정에서 추가로 마크되는 상태가 없음을 의미한다. 결국, 윗식 (5) 와 (6) 으로부터 길이가 n 보다 작은 문자열에 의해서는 구분불가능이면서 길이 n 인 문자열에 의해서는 구분가능해지는 상태가 없음을 의미하는 것이다. 길이 n 인 문자열에 의해 구분가능한 상태가 없다면 길이 n + 1 인 문자열에 의해 구분가능해지는 상태도 존재하지 않으며, 이는 결국 길이 n 이상인 문자열에 의해 구분가능해지는 상태가 존재하지 않음을 의미하게 된다. 결과적으로 위 프로시저의 루프가 종료되었을 때, 모든 구분가능한 상태 쌍들은 마크될 것이다.

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

procedure : reduce

주어진 오토마타 에 대해 다음과 같은 절차에 따라 축소된 dfa 를 구성한다.

1. 모든 구분가능한 상태 쌍들을 검출하기 위해 프로시저 mark 를 사용한다. 이로부터 모든 구분불가능한 상태들의 집합들, 즉 을 찾아낸다.

2. 구분불가능한 상태들의 집합 각각에 대하여, 라벨이 인 의 상태를 생성한다.

3. 다음 형태를 갖는 M 의 각 전이 규칙에 대하여,

     과 가 속하는 집합을 찾아낸다. 만일 이고 이면, 에 다음의 규칙을 추가한다.

4. 초기 상태 은 의 상태들 중 라벨이 0 을 포함하는 상태이다.

5. 는 라벨이 인 i 를 포함하는 모든 상태들의 집합으로 한다.

 예제 15

그림 18 에서 보인 오토마타를 고려해 보자.

단계 2 에서, 프로시저 mark 는 구분가능한 상태 쌍들 를 찾아낸다. 다음으로 단계 3 의 루프를 실행하는 중에, 이 프로시저는 다음을 계산하게 된다.

그리고

이때 가 구분가능한 쌍이므로 도 구분가능한 쌍으로 마크된다. 이와 같은 방법으로 계속 진행하면, 상태 쌍 가 구분가능한 쌍들로 마크되며, 구분불가능한 쌍들은 이 된다. 따라서, 상태 이 구분불가능한 상태들이 되며, 결국 모든 상태들은 집합들 로 분할된다. 프로시저 reduce 의 단계 2 와 3 을 적용하면 그림 19 의 dfa 가 얻어진다.

그림 18

그림 19

 정리 4

임의의 dfa M 이 주어졌을 때 프로시저 reduce 를 적용하면 다음과 같은 성질을 갖는 다른 dfa 을 얻을 수 있다 :

이에 더하여, 은 언어 L(M) 을 인식하는 dfa 들 중 상태의 수가 가장 작은 dfa 가 된다. 이와 같은 의미에서 은 최소 (minimal) dfa 라 한다.

증명 : 이에 대한 증명은 두 부분으로 이루어진다. 그 첫 번째는 프로시저 reduce 에 의해 구성되는 dfa 가 원래의 dfa 와 동치임을 보이는 것이다. 이 증명은 상대적으로 쉬우며, dfa 와 nfa 의 동치성을 증명 때에 사용한 것과 비슷한 귀납적 논증을 사용할 수 있다. 이와 관련하여 증명하여야 하는 사항은 라는 것과 의 라벨이 ... j ... 의 형태라는 것이 서로 필요충분 조건이라는 것이다. 이 증명은 연습문제로 남겨두고자 한다.

두 번째 부분은 이 최소의 상태 수를 가짐을 증명하는 것이며, 이는 조금 더 어렵다. 의 상태들이 이고 가 초기 상태라 가정하자. 과 동치이면서 전이 함수가 , 초기 상태가 인 dfa 이 존재하고, 은 보다 적은 수의 상태들을 갖는다고 가정하자. 에는 도달불가능 상태들이 존재하지 않으므로, 다음과 같은 조건을 만족하는 문자열 이 존재한다 :

하지만, 이 보다 적은 수의 상태들을 가지므로, 이 문자열들 중에는 다음과 같은 조건을 만족하는 문자열이 적어도 두 개 이상 존재해야 한다. 와 이라 하자.

위에서 와 은 구분가능하므로, 가 종료 상태이고 가 비종료 상태인 (또는 그 반대를 만족하는) 문자열 x 가 존재해야 한다. 다시 말해서, 는 에 의해 승인되고, 는 승인되지 않는 문자열 x 가 존재해야 하는 것이다. 하지만, 다음을 보자.

따라서, 은 와 를 모두 승인하거나 모두 거부하게 되며, 이는 과 이 동치라는 가정에 위배된다. 이 모순에 의하여 위에서 가정한 이 존재할 수 없음이 증명된다.

연습문제

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) 에 포함시키고, 다음으로 이 집합에 포함되지 않은 다른 상태에 대해 같은 과정을 반복한다. 이 과정을 더 이상의 상태가 남지 않을 때까지 계속한다. 이 과정을 알고리즘으로 명확하게 기술하고, 이 알고리즘이 원래의 상태들의 집합을 동치 집합들로 분할함을 증명하라.