[컴파일러] 12. 오토마타

5/12 5/18

 

인식기(Recognizer): 입력으로 string을 받아 그 언어의 문장이면 "YES", 아니면 "NO"를 출력하는 프로그램

튜링머신(type0)-A에 선형 종속(type1)-푸시다운 오토마타(type2)-유한 오토마타(type3)

 

유한 오토마타(Finite Automata. FA)

알파벳Σ에 대한 유한 오토마타 M = (Q,Σ, δ, q0, F)

• Q: state의 유한 집합
• Σ: 입력 알파벳의 유한 집합
• δ: 사상함수
• q0 ∈Q: 시작 상태
• F ⊆Q: 종결 상태의 집합

사상함수 δ: Q * Σ-> 2^Q

ex) δ(q, a) = {p1, p2...pn}

 

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

결정적이다

- δ(q, a)가 한상태 만을 갖는 경우

- δ(q, a) = {p} 대신에 "δ(q, a)=p"로 표기

- δ(q, a)가 항상 한 개의 다음 상태를 가질 때, M이 완전히 명시

δ함수의 확장

- Q x Σ => Q x Σ*

- δ(q, ε) = q. δ(q,ax) = δ(δ(q,a)x), 여기서 x ∈ Σ*이고 a∈Σ.

한 문장 x의 인식

- 만약 δ(q0, x) = p인 경우, p가 종결 상태에 속할 때 (p∈F).

- M에 의해 인식된 언어; L(M) - {x | δ(q0, x) ∈ F}

 

상태 전이도

• 노드: 유한 오토마타의 각 상태 표시(p, q)
• 전이 상태: 상태 q에서 상태 p로 가는 변화를 나타냄
• 레이블: 전이 때의 입력 문자(a)
• δ(q,a) = p
• 종결 상태는 이중원, 시작 상태는 start지시선으로 표시

DFA의 상태수 최소화

• w ∈ Σ*에 대해 q1에서 w를 다 본 상태가 q3 q2에서 w를 다 본 상태가 q4일 때, q3, q4중 하나만 종결상태일 때, q1과, q2는 구별된다고 말함.

동치관계 구성

1. 전체 상태를 종결 상태와 미종결 상태로 구분
2. 같은 입력에 대해 서로 다른 동치류로 가면, 다른 분할을 하여 새로운 동치류를 만든다.
3. 위를 분할이 더 발생하지 않을 때까지 반복

상태수 줄이는 방법

1. 모든 도달 불가능한 상태는 삭제
2. 동치관계를 만들음
3. fa M' = (Q', Σ, δ', q0', F')를 만들음

 

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

-비결정적: 상태 q에서 입력 심벌 a에 대해 갈 수 있는 상태가 여러 개

-δ(q,a) = {p1, p2, p3 ...pn)

-정의: δ(q0,x)의 상태 p중 F의 상태를 포함하는 경우, 문장 x는 M에 의해 인식된다.

 

 

정규표현의 NFA로의 변환

구성요소 분해: 정규표현을 구성요소 부분식으로 분리하고 다시 규칙에 따라 조합.

 

NFA를 DFA로 전환

필요성: NFA에서 ε전이에 대해 컴퓨터 처리가 어려움.

부분집합 구성 알고리즘 용어

• ε-closuse(s): NFA 상태 s에서  ε전이 만으로 도달가능한 상태 집합
• ε-closure(T): T에 포함된 어떤 상태 s에서 ε전이만으로 도달 가능한 상태집합
• move(T, a): T에 포함되는 어떤 상태 s에서 입력기호 a에 의해 전이되는 상태집합
• Dtran: D에 대한 전이 테이블
• Dstates: D의 상태들의 집합

ε-closure의 계산(DFS 이용)

T안의 상태를 모두 stack에 push

ε-closure(T)를 T로 초기설정

while 스택이 비어있지 않음 do

    begin

        스택에서 t를 pop

        for t에서 ε레이블로 연결 가능한 상태 u do

            if u가 ε-closure(T)안에 없음 then do

                begin

                    u를 ε-closure(T)에 추가

                    u를 스택에 push

                end

    end

 

부분집합 구성 알고리즘

input: NFA N

output: 동일한 언어를 수용하는 하나의 DFA D

 

상태 ε-closure(s0)만을 Dstates에 넣는다.

while Dstates안에 마크가 안된 상태 T가 있다. do begin

    mark T;

    for 각 입력기호 a do begin

        U := ε-closure(move(T,a));

        if U가 Dstates안에 없다 then

            U를 마크하지 않고 Dstates에 추가

        Dtran[T, a] := U

    end

end

 

 

정규언어의 변환 관계

<사진 삽입>

 

유한오토마타와 정규 표현

2단계 접근

• 유한 오토마타에서 정규 문법 구하기
• 정규 문법에서 정규 표현 구하기(정규 표현식 구하기)

유한 오토마타에서 정규 문법 만들기:

• 오토마타의 상태에 입력 문자를 추가한 형태의 문법 기호로 표기

대응 정규문법

G = (V_N, V_T, P, S) 형태.

마지막 기호는 r->ε형태 추가.