[PL] Lexical Analysis : Finite Otomata

1. Regular Language와 Finite Otomata

Regular Expression으로 표현한 언어는 Regular Language이다.

특정 문자열이 주어졌을 때, 그 문자열이 Regular Language에 속하는지 확인할 때 'Finite Otomata'를 이용하여 확인할 수 있다.

즉, 오토마타라는 모델을 이용하여 주어진 문자열이 regular Language L에 속하는지 확인할 수 있다.

2. Finite Otomata의 구조

Finite Otomata란 유한한 상태를 가지는 추상적 기계이다.

Finite Otomata is a mathematical model used to represent the system that have a finite number of states and trasition between those states depending on the inputs.

0) FA (FSM) = (Q, $\sum$, q, F, $\delta$)

1) Q : Finite set of states (모든 상태의 집합)

2) $\sum$ : set of Symbols (알파벳, 즉 Symbol들의 집합)

3) q : start state (q $\in$ Q) (시작 상태. 오로지 하나)

4) F : set of final states (F $\subset$ Q) (종료 상태의 집합. 여러개 있을 수 있다.)

5) $\delta$ : Transition Function ( Q X $\sum$ -> Q') (전이 함수)

3. Email 정규 표현식을 표현하기

1) 이메일 주소를 나타내는 정규표현식 : [a-z]+@[a-z]+.[a-z]+

2) 오토마타 구조

FA (FSM) = (Q, $\sum$, q, F, $\delta$)

Q = {q0, q1, q2, q3, q4, q5} // state

$\sum$ = { a, ... , z, @ , . } //input symbol은 a-z, at(@), dot(.)

q : q0

F : {q5}

transition function : [ (q0, [a-z]) -> q1), (q1, [a-z]) -> q1), (q1, @) -> q2), (q2, [a-z]) -> q3), (q3, [a-z]) -> q3), (q3, .) -> q4), (q4, [a-z]) -> q5), (q5, [a-z]) -> q5) ]

(q0, [a-z]) -> q1 는 q0 상태일 때 symbol a-z 중 하나가 오면, state는 q1으로 변화하는 전이함수이다.

3) jenny@naver.com을 Finite Otomata를 이용하여 구할 수 있다!

• 전이함수의 output과 결과 state가 다르다면, 해당 문자열은 적절한 정규 표현식이 아니라고 판단된다.
• 최종 단계에 도달했을 때, Final State가 아니라면 해당 문자열은 적절한 정규 표현식이 아니라고 판단된다.
• 최종 단계에 도달했을 때, Final State에 해당된다면 적절한 문자열이다.

• PDF 참고자료 참조