6 - Regular Language (Finite Automata)

정규 언어중 유한 오토마타에 대한 개념에 대해 알아보자

이 이론은 컴파일러의 어휘 분석, 즉 가장 핵심적인 부분을 설계하는데 있어서 중요하기 때문에

제대로 이해하고 넘어가는게 좋다.

 

 

 

Finite Automata 구성 요소

---

총 5가지로 이루어져 있다

Q : 가질 수 있는 집합들

π : 가질 수 있는 터미널들

δ : 변화의 과정을 기술하는 함수

q0 : 시작하는 점F : 끝나는 점의 집합

 

다음 예제를 보고 개념을 습득해보자각각 순서대로 위의 인자라고 생각하면 된다.({q0,q1,q2},{a,b},δ,q0,{q2})F , 끝나는 점이 집합인 이유는 여러개 일 수 있기 때문이다.

 

δ(q0,a) = q1, δ(q0,b) = q2, δ(q1,b) = q0, δ(q2,a) = q0 가 주어졌을때,

δ(q0,a) = q1 는 q0 노드에서 a 경우일때 q1으로 간다는 뜻이다.

위 식을 그림으로 나타내면 이와 같은 형태가 된다.

만약 여기서 abba가 주어진다면?

q0 -> q1 -> q0 -> q2 -> q0 가 되고

목적지에 도달하지 않았기 때문에 이 식에서는 틀린 문장이다.

 

이론적인 것에서 이해를 돕기 위하여 C언어 변수 이름 규칙 오토마타를 한번 보도록 하자

 

처음에는 무조건 문자열이 와야 한다. 숫자가 오면 성립하지 않는다.

첫번째가 문자열인 이후에는 문자, 숫자 둘다 가능하다.

이런 식으로 활용할 수가 있다.

 

다음은 소수점 표기에 대한 오토마타이다.

처음엔 숫자가 무조건이다. 그 후에는 .이 나올때까지 계속 숫자가 나와도 되며,

.이 나오고 난뒤 바로는 또 무조건 숫자다.

그 이후로는 소수점 아래로 계속 숫자가 나와도 된다.

 

 

예제를 통해 유한 오토마타에 대한 개념을 알아보았다.

다음엔 결정지가 한곳이 아닌 Non-Deterministic Finite Automata, NFA에 대해 알아보자