정규언어(후반부)
이 글은 <컴파일러 입문>을 참고하여 만들어졌습니다.
3.3.4 DFA의 상태수 최소화
DFA의 상태수 최소화(state minimization)는 DFA를 이용하는 어휘 분석기의 상태 전이표의 크기를 줄임으로써 기억 공간을 적게 차지하도록 하고 또한 어휘 분석 프로그램을 간단히 하는데 큰 도움을 준다.
상태수를 최소화하는 방법은 등치 관계(equivalence relation)을 이용하여 상태들을 합침(state merge)으로써 상태수를 최소화하는 것이다.
따라서 구별되지 않는 상태들은 같은 형태의 입력 스트링을 인식하기 때문에 모두 합칠 수 있다.
다음은 동치 관계를 이용하여 구별되지 않는 상태들을 하나의 상태로 합치는 방법이다.
- DFA의 상태 집합을 동치 관계에 의해 분할하고 각 동치류를 최소화한 유한 오토마타 상태(Q')로 놓는다.
- 그리고 시작 상태(q0')는 DFA의 시작 상태가 포함되어 있는 동치류가 되며 종결 상태의 집합(F')은 DFA의 종결 상태가 포함되어 있는 동치류로 구성된다.
- 마지막으로, 전이함수 δ'은 δ 함수에 의해 계산된다.
다음 조건을 만족하는 유한 오토마타를 축약된 유한 오토마타(reduced finite automata)라 부른다.
(1) 모든 상태가 시작 상태로부터 도달 가능하다(accessible).
(2) 모든 상태가 서로 구별 가능하다(distinguishable).
축약된 유한 오토마타로 변환하는 방법은 아래와 같다.
단계1. 어떤 상태로 들어오는 지시선 없이 나가는 지시선만 갖는 도달 불가능한 상태(inaccessiblestate)는 모두 제거한다.
단계2. 동치관계를 이용하여 구별되지 않는 상태들을 하나로 합친 후 최소화한 유한 오토마타를 구성한다.
3.3.5 유한 오토마타의 닫힘 성질
유한 오토마타 언어(FAL: Finite Automata Language)란 유한 오토마타에 의해 인식되는 언어의 종류
[정리 3.3]은 유한 오토마타 언어가 합집합, 접속 그리고 클로저 연산에 대하여 닫혀있다는 것을 의미한다.
두 개의 유한 오토마타가 나타내는 언어의 합집합을 인식하는 유한 오토마타를 구성하는 방법은 다음과 같다.
1. 새로운 시작 상태를 만들어 각각의 유한 오토마타에 마치 각 유한 오토마타의 시작 상태에서 온 것처럼 연결한다.
2. ε을 인식하면 새로 만든 시작 상태로 종결 상태로 만든다.
Section 3.4 정규 언어의 속성
3.4.1 정규 문법과 유한 오토마타
정규 문법이 생성하는 언어와 같은 종류의 언어를 인식하는 유한 오토마타가 존재한다.
<=> 역으로 유한 오토마타가 인식하는 언어와 같은 종류의 언어를 생성하는 정규 문법이 존재한다.
- 주어진 정규 문법에 대해서 동등한 언어를 인식하는 유한 오토마타를 구성하는 방법은 유한 오토마타의 각 요소들을 대응되는 문법의 요소를 이용하여 정의를 해주는 것이다.
- 유한 오토마타의 상태 집합은 nonterminal 심벌의 집합에다 새로운 종결 상태를 더한 것이 된다.
- 문법의 nonterminal 심벌 집합에는 종결 상태에 해당하는 것이 없으므로 새로운 종결 상태를 하나 도입하게 된다.
그리고 시작 상태는 시작 심벌이 되고 각 생성 규칙에 해당하는 전이 함수가 정의된다.
문법 G가 생성하는 언어에 ε이 포함되어 있으면, 시작 상태가 종결 상태가 되어야만 ε을 인식할 수 있게 된다.
또한, 새로 구성된 유한 오토마타의 δ 함수의 개수는 정규 문법의 생성 규칙의 개수와 같다. 즉 |δ| = |P|이다.
생성 규칙 A -> aB의 의미는 nonterminal A가 terminal a를 생성하고 연속해서 nonterminal B로부터 유도되는 스트링을 생성하는 것이다.
따라서, 유한 오토마타의 δ(A, a)의 다음 상태로 B가 될 수 있는 의미와 같다.
- 왜냐하면, δ(A, a)의 다음 상태에 B가 포함된다는 것은 상태 A에서 입력 심벌 a를 보고 B 상태로 이동하고 계속해서 B 상태에서 입력을 받아들일 수 있다는 의미이기 때문이다.
- 또한 생성 규칙 A -> a의 의미는 nonterminal A가 terminal a를 생성하고 유도 과정이 끝나기 때문에 δ(A, a)의 다음 상태에 종결 상태가 포함되어야 하는 이유이다.
다시 말해서, nonterminal 집합은 상태 집합으로,
terminal 집합은 입력 심벌로, 시작 심벌은 시작 상태로 각각 구성된다.
전이 함수 δ(q, a) = r에 대하여 생성 규칙 q -> ar를 만들고 또한 각 종결상태 q에 대하여 q -> ε인 생성 규칙을 추가한다.
결국 변환된 정규 문법의 생성 규칙의 개수는 전이 함수의 개수(상태 전이도에서는 지시선의 개수)에다 종결 상태의 개수를 더한 것이 된다.
3.4.2 유한 오토마타와 정규 표현
유한 오토마타가 인식하는 언어를 정규 표현으로 나타낼 수 있고 역으로 주어진 정규표현을 인식하는 유한 오토마타를 고안할 수 있다.
다음은 유한 오토마타에서 정규 표현을 얻는 과정이다.
1. 유한 오토마타로부터 정규 문법을 구한다.
2. 구한 정규 문법으로부터 정규 표현을 얻는다.
첫째, 유한 오토마타에서 상태 전이표를 구성한다.
둘째, 상태 전이표를 정규 문법으로 변환한다.
또한, 각 종결 상태에 대해서는 ε-생성 규칙을 추가한다.
셋째, 정규 문법을 정규 표현식으로 바꾼다.
넷째, 정규 표현식을 풀어서 정규 표현으로 나타낸다.
결론적으로, 유한 오토마타가 인식하는 언어를 정규표현으로 나타내는 방법은 우선 오토마타를 정규 문법으로 바꾸고 그 정규 문법을 풀음으로써 정규표현을 구하게 된다.
이제 역으로, 주어진 정규표현을 인식하는 유한 오토마타를 고안하는 과정을 살펴보자.
- 정규 표현의 정의로부터 NFA(ε-NFA)를 구성한다.
- 간단화 방법을 적용할 수 있으면 적용하여 크기를 줄인다.
- ε-NFA를 DFA로 변환한다.
정규표현의 정의로부터 ε-NFA를 구성하는 방법은 다음과 같다.
먼저, 정규 표현을 이루고 있는 기본 소자에 대한 NFA를 만든 후 연산자에 따라 기본 소자에 대한 NFA를 결합해야 한다.
(1) ε을 인식하기 위해서는 2개의 상태가 필요하며 다음이 ε을 인식하는 NFA이다.
(2) 하나의 입력 심벌을 인식하기 위해서는 두 개의 상태가 필요하며 다음이 a를 인식하는 FA이다.
다음은 정규 표현 N1+N2, N1*N2, N*에 대해 다음과 같이 결합한다.
(1) N1+N2를 구성하는 방법은 새로운 두 개의 상태 i,f를 추가하여 상태 i에서는 N1과 N2의 시작 상태로 ε-전이를 각각 그린다. 또한 각 종결상태에서 f로 가는 ε-전이를 만든다. 그러면 i가 시작 상태이고 f가 종결 상태가 되며, 합집합을 인식하는 ε-NFA가 작성된 것이다
(2) N1N2를 구성하는 방법은 N1의 시작 상태가 접속된 정규 표현을 인식하는 ε-NFA의 시작 상태가 되며 전체의 종결 상태가 된다. 그리고 접속을 인식해야 하기 때문에 N1의 종결 상태에서 N2의 시작 상태로 가는 ε-전이를 그린다.
(3) N이 주어졌을 때, N*를 인식하는 ε-NFA는 2개의 상태를 추가하여 다음과 같이 지시선을 연결하면 된다.
위의 규칙을 이용하여 만들어지는 ε-NFA는 많은 ε-전이를 갖고 있으므로 만드는 과정에서 다음과 같은 간단화(simplification)방법을 적용할 수 있다.
3.4.3 정규 언어의 닫힘 성질
정규 언어를 표현할 수 있는 방법이 정규 문법, 정규 표현, 유한 오토마타 등이 있기 때문에 정규 언어에 대한 속성은 어떤 방법을 이용하여 증명하여도 맞는다.
위 정리에서, 정규 언어는 합집합, 접속, 그리고 클로저에 대하여 닫혀 있다는 것을 알 수 있다.
3.4.4 정규 언어에 대한 펌핑 렘마
펌핑 렘마(Pumping Lemma)는 정규 언어의 속성으로서 어떤 언어가 정규 언어가 아님을 증명하는데 유용한 보조 정리로 다음과 같다.
위 정리의 의미는 길이가 충분히 큰 스트링이 정규언어에 속하려면 반드시 xyz의 형태로 나타낼 수 있으며, 또한 xy^iz도 그 정규 언어에 속한다는 것이다.
참고
[정리 3.5]의 증명 과정에서 w의 길이가 상태수와 같거나 큰 경우에 같은 상태를 2번 경유하게 된다.
따라서 w의 길이가 상태수와 같거나 크다고 언급해야 되나 그냥 상태수보다 크다고 말하였다.
왜냐하면 이 경우도 성립하기 때문이다.
또한 유한 오토마타는 반복되는 심벌의 개수를 셀 수 없기 때문에 정확히 세는 언어는 인식할 수 없다.