유한 오토마타

유한 오토마타

어떤 알파벳  Σ로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개이다.

컴퓨터의 여러 분야에서 널리 사용되고 있다.
특히 플립플롭(flip-flop)을 비롯한 여러 컴퓨터 관련 고안물들, 형식언어의 연구, 그리고 컴파일러 등에 유용하게 쓰인다
또, 컴파일러의 어휘 분석(lexical analysis) 또한 유한 오토마타의 대표적인 것이다.

상태 전이 함수의 형태에 따라 결정적 유한 오토마타 (Deterministic Finite Automata; DFA)와 비결정적 유한 오토마타(Nondeterministic Finite Automata; NFA)를 구분한다.
오토마타의 전이 함수는 유한 오토마타의 상태 전이를 행렬(matrix)로 표시한 상태 전이표(state transition table)로 표시되어진다.

• ε에 의한 상태 전이를 ε-전이라고도 한다.

전이 함수의 확장

문자열 인식에 어려움이 있기 때문에, 전이 함수를 아래와 같이 확장하는 것이다.(얼마나 편해!)

예제 3.44와 3.45에서 알 수 있듯이 이런 형태로 전이 함수를 적용하면 NFA에 의해 인식되는 문장졀이 무엇인지 명확하게 알지 못한다.
이를 위해 다음과 같이 전이 함수를 하나의 입력 기호에서 입력 문자열로 확장해보자

표현 방법

비형식적 표현 : 상태 전이도

상태 전이도는 그래프를 통하여 쉽게 개념이 들어와 유한 오토마타를 설명 할 때 상태 전이도로 많이 사용한다

상태 전이도란, 오토마타의 각 상태(state)를 노드(node)로 표현한다

이동함수 f(q,a)=p에 대해서는 상태 q에서 p로 가는 라벨(label)이 a인 간선(edge)으로 표기한다
최종 상태들은 이중원(double circle) 으로 나타내고, 시작 상태는 시작 간선으로 표시하는 유향그래프(directed graph) 이다.

형식적 표현 : 5가지 구성 원소로 표현

유한 오토마타를 형식적으로 표현하면 5-튜플(tuple)로 구성 할 수 있다.

결정적 유한 오토마타(DFA)

DFA는 다음의 두 가지 조건을 만족해야 한다.

1. ε에 의한 상태전이(state transition)가 없어야 한다.
2. δ(q, a) = {P1, P2, …, Pn} 에서 n = 1 이다.

• 즉, δ : Q x Σ → Q
  다시 말하면, 임의의 상태에서 하나의 입력 기호에 대해서 다음 상태는 오직 하나이거나 상태 전이가 없어야 한다.

비결정적 유한 오토마타 (NFA)

ε에 의한 상태 전이가 있거나
δ(q, a) = {P1, P2, …, Pn}에서 n ≥ 2인 n이 하나라도 존재한다.

즉 `δ : Q x Σ → 2Q
어떤 상태에서 하나의 입력기호에 대해서 다음 상태가 두 개 이 상인 것이 하나라도 존재한다

예제

예제 3.30 상태전이도로 표현하기 1

유한 오토마타가 문자열 aabb를 인식할 수 있는지 살펴보자.

시작 상태 q0에서 입력 a를 만나면 q0 상태를 유지하고, 다음 문자인 a를 입력받으면 q1 상태 로 전이한다.
그리고 q1 상태에서 다음 입력인 b를 받으면 q2 상태로 전이하고,
다시 b를 입력받으면 q3 상태로 전이한다.
입력을 모두 읽은 후의 상태가 q3이므로 문자열 aabb 는 주어진 유한 오토마타에 의해 인식된다.

하지만 문자열 aabb가 이런 식으로만 되는 것은 아니다.

예제 3.31 상태 전이도로 표현하기 2

시작 상태인 q0에서 시작하여 a, b, …, z 등의 영문자가 나오면 다음 상태이자 최종 상태인 q1로 가 서 종료될 수 있다.
계속해서 영문자 a, b, …, z나 숫자 1, 2, …, 9 등이 나오 면 다시 반복할 수 있다는 의미이다.

예제 3.32 형식적으로 표현하기 1

정규 표현 (a + b)*abb 를 인식하는 유한 오토마타를 형식적으로 표현하라

예제 3.33 형식적으로 표현하기 2

첫 번째 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 소문자나 숫자이며, 길이에 제한이 없는 식별자를 인식하는 유한 오토마타를 형식적으 로 표현하라

예제 3.33.1 상태 전이표로 표현하기

예제 3.33의 전이 함수는 매우 길기 때문에 이를 간단하게 나타내기 위해 **상태 전이표(state transition table)**를 도입한다.

상태 전이표는 유한 오토마타의 상태 전이를 행 렬(matrix)로 나타낸 것으로, 행렬의 행과 열은 각각 상태 집합과 입력 기호를 나타내고 행과 열이 교차하는 위치에 다음 상태를 기록한다.
만약 전이 함수가 상태와 입력에 해당하 는 위치에 값이 없다면 상태 전이표에서 그 위치에 ø을 넣는다.

위의 문제를 상태 전이표로 나타내면 아래와 같이 나타낼 수 있다.

예제 3.34 DFA 확인하기 1

예제 3.33의 유한 오토마타가 DFA인지 알아보자

[예제 3-33]의 유한 오토마타는 ε에 의한 상태 전이가 없고, 임의의 상태에서 하나 의 입력에 대해 다음 상태가 단 하나이므로 DFA이다.

예제 3.36 DFA 확인하고 상태전이도로 표현하기

0과 1이 짝수 개인 문자열을 받아들이는 다음과 같은 유한 오토마타가 DFA인지 알아보고 상태 전이도로 표현해보자

M = (Q, Σ, δ, q0, F)
단, Q = {q0, q1, q2, q3}
Σ = {0, 1} q0 = q0
F = {q0}

예제 3.37 DFA로부터 문장인식하기

[예제 3-33]의 식별자를 인식하는 유한 오토마타는 DFA인데 이 DFA로부터 문장 a12를 인식해보자.

시작 상태가 q0이므로 다음과 같은 과정을 거친다.

δ(q0, a) = q1
δ(q1, 1) = q1
δ(q1, 2) = q1

모든 입력을 읽은 후 마지막에 도달한 상태가 q1이며, 최종 상태가 q1이므로 a12는 주어진 DFA에 의해 인식된다.

DFA로 부터 문장 인식하기 2 - PPT X

위의 식별자를 인식하는 유한 오토마타는 DFA인데 이 DFA로부터 문장 a12를 인식해보자.
시작 상태가 q0이므로 다음과 같은 과정을 거친다.

δ(q0, a) = q1
δ(q1, 1) = q1
δ(q1, 2) = q1

모든 입력을 읽은 후 마지막에 도달한 상태가 q1이며, 최종 상태가 q1이므로 a12는 주어진 DFA에 의해 인식된다.

DFA로 부터 문장 인식하기 3

[예제 3-36]의 DFA로부터 0101을 인식하는 과정을 알아보자.

위의 DFA로부터 0101을 인식하는 과정을 알아보자
시작 상태가 q0이므로 다음과 같은 과정을 거친다.

δ(q0, 0) = q2
δ(q2, 1) = q3
δ(q3, 0) = q1
δ(q1, 1) = q0

모든 입력을 읽은 후 마지막에 도달한 상태가 q0이며, 최종 상태가 q0이므로 0101은 주어진 DFA에의해 인식된다.

예제 3.40 DFA로 부터 문장 인식하기 4

앞선 예제(DFA로 부터 문장 인식하기 2)에서 확장된 함수에 의해 문장 a12를 인식하는 과정을 살펴보자.

δ*(q0, a12) = δ(δ*(q0, a1), 2)
= δ(δ(δ(q0, a), 1), 2) = δ(δ(q1, 1), 2)
= δ(q1, 2)
= q1 ∈ F

그러므로 a12는 인식된다. 이는 다음과 같은 방법으로도 인식할 수 있다.

δ*(q0, a12) = δ*(q1, 12) = δ(q1, 2)

= q1 ∈ F

연속적으로 문장이 인식 됨에 따라 상태를 치환하면서 확장하는 것이다

예제 3.43 NFA인지 확인하고 상태전이도로 표현하기

2개의 연속적인 0이 있거나, 2개의 연속적인 1이 있는 문자열을 받아들이기 위한 유한 오토마타는 다음과 같다.
NFA인지 알아보고 형식적으로 표현해보자

전이 함수 중 δ(q0, 0) = {q0, q3}이므로 NFA이다.
이를 형식적으로 표현하면 다음과 같다.

M = (Q, Σ, δ, q0, F)
단, Q = {q0, q1, q2, q3, q4}
Σ = {0, 1}

q0 = q0  
F = {q2 , q4}

예제 3.44 NFA부터 문장 인식하기

유한 오토마타가 문장 baabb를 인식하는지 알아보자

인식하는 과정을 2 가지 방법으로 풀어 볼 수 있다

1. 하나 하나 전이 함수를 적용하여 인식하는 방법

δ(q0, b) = {q0}이 된다….(1)
δ(q0, a) = {q0, q1}이 된다….(2)
δ(q0, a) = {q0, q1}이 된다….(3)
δ(q0, b) = {q0}이 된다….(4)
δ(q0, b) = {q0}이 된다….(5)

입력 문자열을 다 읽은 후 최종 상태는 {q0}이 되었지만 최종 상태가 {q3}이므로 주어진 문자열은 인식되지 않는다고 해야 한다.

그러나 NFA에서는 이런 결론에 문제가 있다. 아직도 적용하지 않은 상태가 많이 남아 있기 때문이다.

즉 (2)에서의 q1 상태, (3)에서의 q1 상태 등이다.
이 모든 상태를 적용해야하는데 그렇게하려면 어떤 순서로 해야 하는지도 고려해야 할 것이다.

여기서는 (2)에서 q 상태부터 적용하겠다.
이것 또한 최종 상태에 도달하지 못한다. 이번에는 (3)에서 q1 상태부터 적용하겠다.
δ(q1, b) = {q2}가 된다.
δ(q2, b) = {q3}이 된다.

모든 입력을 읽은 후 마지막에 도달한 상태가 {q3}이고 최종 상태가 {q3}이므로 문장 baabb는 주어진 NFA에 의해 인식된다.

2. 그림으로 표현하는 방법

이 경우는 시작 상태에서 출발하여 도달 가능한 모든 상태를 나타내는 것이다. 이 중에서 입력 문자 열 baabb를 모두 읽은 후 도달 가능한 상태는 {q0, q3}이다.

∴ {q0, q3} ∩ F = {q3}
∴ 문장 baabb는 주어진 NFA에 의해 인식된다.

예제 3.45 NFA로부터 문장 인식하기

[예제 3-43]의 NFA로부터 문장 0011을 인식하는지 알아보자.

• δ(q0, 0) = {q0, q3}이 된다….(1)
  • 상태가 2개이므로 이 중에서 현재 상태를 q0으로 선택하자.
• δ(q0, 0) = {q0, q3}이 된다….(2)
  • 상태가 2개이므로 이 중에서 현재 상태를 q0으로 선택하자.
• δ(q0, 1) = {q0, q1}이 된다….(3)
  • 상태가 2개이므로 이 중에서 현재 상태를 q0으로 선택하자.
• δ(q0, 1) = {q0, q1}이 된다….(4)

입력 문자열을 다 읽은 후 최종 상태는 {q0, q1}이 되었다.
그러나 최종 상태는 {q2, q4}이 므로 주어진 문자열은 인식되지 않는다.

이번에는 적용하지 않은 상태 중 (1)에서 q3 상태부터 적용하겠다.

• δ(q3, 0) = {q4}가 된다.
• δ(q4, 1) = {q4}가 된다.
• δ(q4, 1) = {q4}가 된다.
  최종 상태는 {q2, q4}이므로 문장 0011은 주어진 NFA에 의해 인식된다.

그림으로 표현해보자

시작 상태에서 출발하여 입력 문자열 0011을 모두 읽은 후 도달 가능한 상태는 {q0, q1, q2, q4}이다.

∴ {q0, q1, q2, q4} ∩ F = {q2, q4}
∴ 문장 0011은 주어진 NFA에 의해 인식된다.

예제 3.46 NFA로부터 문장 인식하기 3

[예제 3-44]에서 문장 baabb에 대해 확장된 전이 함수에 적용해보자.

δ(q0, baabb) = δ(q0, aabb)  
	= δ(q0, abb) ∪ δ(q1, abb)
	= {δ(q0, bb) ∪ δ(q1, bb)} ∪ø 
	= δ(q0, b) ∪ δ(q2, b)  
	= {q0} ∪ {q3}  
	= {q0, q3}
∴ {q0, q3} ∩ F = {q3}

위의 ø 은 δ(q1, abb)로 더 이상 갈 곳이 없음을 나타낸다

레퍼런스

• 오토마타

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>