컴파일러구성 - [제3장]정규언어와 유한오토마타

컴파일러구조 - 정규언어와 유한오토마타

용어정리

1. 유한 오토마타 : 어떤 알파벳 T로부터 만들어 지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템이 변화할 수 있는 상태가 유한개인 것
2. 비결정적 유한 오토마타 NFA: 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈수 있는 다음 상태가 두개 이상 존재할 수 있는 유한 오토마타
3. 결정적 유한 오토마타 DFA : 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결졍되는 것
4. 상태전이도(transition diagram) :오토마타의 각 상태(state)를 노드(node)로 나타내며, 이동함수 δ(q,a) ＝ p에 대해서는 상태 q에서 p로 가는 레이블(label)이 a인 지시선(directed arc)으로 표기. 또한 종결상태들은 이중 원(double circle)으로 나타내고, 시작상태는 시작지시선으로 표시하는 유향 그래프(directed graph)
5. 상태 : 오토마타에서 입력기호에 의하여 전이된 것을 상태라 하며 상태전이도에서 원으로 표현한다.

요점정리

유한 오토마타(finite automata)란 어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템의 변화할 수 있는 상태가 유한개인 것이다. 

유한 오토마타는 입력으로 문자열을 받아서, 그 문자열이 그 언어의 문장이면 "yes"를 답하고 그렇지 않으면 "no"라고 답하는 프로그램으로 어휘분석기는 유한 오토마타의 대표적인 예이다. 

유한 오토마타를 표현하는 방법에는 두 가지가 있다. 먼저, 정의에 따라서 5가지의 구성원소들을 형식(formal)에 맞게 정확히 표현하는 방법이 있다. 다음으로는 상태전이도(transition diagram)를 사용하여 비형식적(informal)으로 표현하는 방법인데 그림을 통하여 쉽게 개념이 들어오기 때문에 일반적으로 유한 오토마타를 설명할 때 상태전이도를 많이 사용한다. 

유한 오토마타는 결정적 유한 오토마타(Deterministic Finite Automata : DFA) 와 비결정적 유한 오토마타(Nondeterministic Finite Automata; NFA)로 나뉘어진다. 

결정적 유한 오토마타(DFA)란 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결정되는 유한오토마타이다. 

비결정적 유한 오토마타(NFA)란 두 가지가 있는데 먼저, ε 에 의한 전이가 있는 경우와 다음으로 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈 수 있는 다음 상태가 두 개 이상 존재할 수 있는 유한 오토마타이다. 

NFA는 언어의 구조를 쉽게 표현할 수 있지만 DFA보다 프로그램으로 구현하기 힘들다. 반면 DFA는 NFA보다 프로그램으로 구현했을 때 효율면에서 좋다. 이러한 이유로 NFA가 언어의 구조를 표현하고 일반적인 구현은 DFA로 해야 효율적이다. 따라서 DFA에서 NFA로, NFA에서 DFA로의 변환을 필요로 하며 서로 변환 가능하다.

DFA 는 상태수를 최소로 줄일 수가 있다. 이렇게 해서 컴파일러의 효율을 높이는 것이다. 

정규 표현, 정규 문법, 유한 오토마타는 서로 동치관계에 있으며 서로 변환 가능하다.

연습문제

• 

  다음의 오토마타가 인식할 수 없는 문자열은?
  

  연습문제 설명

  

  답을 체크하세요

  1. aa
  2. aba
  3. abaa
  4. babc

  정답 :

  ②

  aa, abaa, babc 등은 모두 종료상태인 S2 에서 끝난다.
  그러나 aba 는 다음과 같이 S1에서 끝난다.
  δ(S0, aba) = S1
  δ(S1, ba) = S0
  δ(S0, a) = S1 

• 

  다음은 오토마타를 구현한 파스칼 프로그램의 일부이다.
  프로그램의 진행으로 보아서 전이함수표가 작성되는 곳은?
  

  연습문제 설명

  

  
  program DFA(input, output);
  :
  function delta(s : state ; c : sigma) : state ;
  function deltabar(s : state) : state ;
  function accept : boolean ;
    begin

      accept :＝ deltabar(s0) in finalstate
    end ;
  procedure initialize ;
  :
  begin {Start main program DFA.}
    initialize ;
    if accept then
                 writeln('accepted') ;
             else
                 writeln('rejected') ;
   end.

  답을 체크하세요

  1. delta
  2. deltabar
  3. accept
  4. initialize

  정답 :

  ④

  프로그램의 구성을 보면 Procedure initialize 가 가장 먼저 실행이 된다.
  따라서 이 곳에서 전이함수표가 만들어져야 한다.

• 

  오토마타를 볼 때 밑줄친 finalstate 의 값은?
  

  program DFA(input, output);
  :
  function delta(s : state ; c : sigma) : state ;
  function deltabar(s : state) : state ;
  function accept : boolean ;
    begin

      accept :＝ deltabar(s0) in finalstate
    end ;
  procedure initialize ;
  :
  begin {Start main program DFA.}
    initialize ;
    if accept then
                 writeln('accepted') ;
             else
                 writeln('rejected') ;
   end.

  답을 체크하세요

  1. S0
  2. S1
  3. S2
  4. S0,S2

  정답 :

  ③

  S2는 종료상태이다. 

• 

  다음은 NFA를 DFA로 변환하는 과정이다. ε-closure(6)을 구하면?
  

  연습문제 설명

  

  
  

  답을 체크하세요

  1. 6,7
  2. 1,2,4,6
  3. 1,2,4,6,7
  4. 0,1,2,4,6,7

  정답 :

  ③

  6을 출발점으로ε 으로 연결되는 상태는 7,1,2,4 이므로
  ε-closure(6)= 1,2,4,6,7

• 

  다음은 NFA를 DFA로 바꾸는 과정이다. 빈칸 ‘가’에 알맞은 것은?
  

  연습문제 설명

  NFA M=()
  

  δ	0	1
  q0	{q0,q1}	{q0}
  q1	φ	{q0,q1}

  
  변환된 DFA의 상태전이 함수는 다음과 같다.
  

  δ'	0	1
  [q0]	[q0,q1]	[q0]
  [q1]	φ	[ ‘가’ ]
  [q0,q1]	[ ‘나’ ]	[q0,q1]

  
  

  답을 체크하세요

  1. φ
  2. [q₀]
  3. [q₁]
  4. [q₀,q₁]

  정답 :

  ④

  앞의 δ함수표에서 q₁ 에서 1을 보면 {q₀,q₁}이다. 따라서 δ' 함수표에서도 [q₀,q₁] 가 된다. 

• 

  다음은 NFA를 DFA로 바꾸는 과정이다. 빈칸 ‘나’에 알맞은 것은?
  

  연습문제 설명

  NFA M=()
  

  δ	0	1
  q0	{q0,q1}	{q0}
  q1	φ	{q0,q1}

  
  변환된 DFA의 상태전이 함수는 다음과 같다.
  

  δ'	0	1
  [q0]	[q0,q1]	[q0]
  [q1]	φ	[ ‘가’ ]
  [q0,q1]	[ ‘나’ ]	[q0,q1]

  
  

  답을 체크하세요

  1. φ
  2. [q₀]
  3. [q₁]
  4. [q₀,q₁]

  정답 :

  ④

  δ함수표에서
  먼저, q₀ 에서 0을 보면 {q₀,q₁} 이다.
  다음으로 q₁ 에서 0을 보면 역시 {q₀,q₁} 이다.
  따라서 이들을 합한 것도 {q₀,q₁} 이다.
  그러므로 δ' 함수표에서도 [q₀,q₁] 이 된다.