컴파일러구성 - [제4장]정규문법,정규표현과 결정적 유한오토마타[DFA] 의 동치관계

컴파일러구조 - [제4장]정규문법,정규표현과 결정적 유한오토마타[DFA] 의 동치관계

DFA 상태수 최소화 동치관계 증명

융어정리

1. 동치관계 : Equivalence relation, 반사적이고, 대칭적이고, 추이적인 관계를 만족하는 관계, 정규문법-> 정규표현->유한오토마타 관계가 성립하고 다시 유한오토마타-> 정규문법이 성립하므로 동치관계를 만족한다.
2. 동치류 : 서로 동치(同値)인 것을 하나로 모은 집합.
3. 유한 오토마타 : 어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템의 변화할 수 있는 상태가 유한개인 것
4. 정규문법 : A→tB A→t (우선형) 또는 A→Bt A→t(좌선형) 단, t ∈ V*t
5. 정규표현 : 정규문법을 가장 잘 표현할 수 있는 표현법. 주로 터미널 기호들이며 터미널 기호들이 +(or), *(closure), +(dagger), 등으로 표현된 것들이다.

요점정리

1. NFA는 언어의 구조를 쉽게 표현할 수 있지만, DFA보다 프로그램으로 구현하기 힘들다. 반면 DFA는 NFA보다 프로그램으로 구현했을 때 효율면에서 좋다. 이러한 이유로 NFA가 언어의 구조를 표현하고 일반적인 구현은 DFA로 해야 효율적이다. 따라서 DFA에서 NFA로, NFA에서 DFA로의 변환을 필요로 하며 서로 변환 가능하다.
2. 유한오토마타는 프로그램으로 구현이 가능하다는 것을 보장해 주는 수학적 모델이다. 따라서 유한오토마타는 언제나 프로그램으로 구현이 가능하다.
3. 정규문법 정규표현, 유한 오토마타는 서로 동치관계에 있다. 따라서 정규문법은 정규표현으로 변환이 가능하고 정규표현은 유한오토마타로 변환이 가능하다. 그리고 유한오토마타는 정규문법으로 변환이 가능하다.
4. 수학에서 집합 X에서의 동치관계는 X에서의 반사적이고, 대칭적이고, 추이적인 이항관계를 말한다.
   즉, 관계를 ~으로 표기할 때, X의 임의의 원소 a, b and c 에 대해 다음이 성립한다.
   
   반사율: a ~ a, 대칭율: 만약 a ~ b 이면, b ~ a
   추이율: 만약 a ~ b 이고, b ~ c 이면, a ~ c
   
   동치관계는 어떠한 기준으로인가 비슷한 개체들을 무리 짓는데 사용된다.
5. 동치관계 정리
   정규문법 => 정규문법 (역도 성립한다. 즉 반사율)
   
   정규문법=> 정규표현, 정규표현=> 유한오토마타=> 정규문법이므로
   따라서 정규표현=>정규문법도 성립한다.(대칭율)
   
   정규문법=>정규표현, 정규표현=>유한오토마타, 따라서 정규문법=> 유한오토마타도 성립한다.(추이율) 

연습문제

• 

  정규방정식 S = bS + a의 해는?

  답을 체크하세요

  1. b^*a
  2. a
  3. b
  4. ba^*

  정답 :

  ①

  α,β가 정규표현이고 ε∉α이면,
  X =αX+β의 유일해(unique solution)는 X =α^*β이다.
  즉 X를 S로 α를 b로, a를 β로 바꾸면 b^*a이다.

• 

  다음 중 나머지 셋과 다른 것은?

  답을 체크하세요

  1. 정규문법
  2. 유도트리
  3. 정규표현
  4. 유한오토마타

  정답 :

  ②

  정규문법과 정규표현 그리고 유한 오토마타는 모두 동치관계가 성립한다. 따라서 관계없는 것은 유도트리가 된다. 

• 

  다음은 정규문법을 정규표현 방정식으로 변환하는 과정이다.
  ‘가’ 에 알맞은 것은?
  

  G₂=({S,A,B}, {0,1}, P,S)
                P : S → 1A｜0
                     A → 0A｜1B
                     B → 1B｜0
           정규표현 방정식으로 나타내면
              S = 1A+0 ……………①
              A = 0A+1B ……………②
              B = 1B+0 ……………③
           ③식에서 B =     ‘가’    
           이것을 ②식에 대입하면 A = 0^*11^*0
           따라서
              S = 10^*11^*0+0

  답을 체크하세요

  1. 1^*
  2. 1^*0
  3. 0^*1
  4. 010^*

  정답 :

  ②

  B=1^*0

• 

  다음은 주어진 문법을 정규표현으로 변환하는 과정이다.
  촘스키의 분류에 따르면 어디에 속하는가?
  
  

  연습문제 설명

  G ＝ ({S, A, B}, {a, b}, P, S)
    P: S －－→  aA | bS
        A －－→  aS | bB
        B －－→  aB | bB | ε
  
    <풀이> 생성규칙을 정규표현 방정식으로 변환하면
        S ＝  aA ＋ bS         ------ ①
        A ＝  aS ＋ bB         ------ ②
        B ＝  aB ＋ bB ＋ ε    ------ ③ 이다.
      ③번식에서
         B ＝   (a ＋ b)^＊  ------------- ④
       ②식을 대입하여 ①식을 풀면
      S ＝   aaS ＋ abB ＋ bS ----- ⑤
      여기에 ④ 식을 대입하면 풀면
       S ＝ (aa ＋ b)^＊ab(a ＋ b)^＊ 가 된다.

  답을 체크하세요

  1. type 0
  2. type 1
  3. type 2
  4. type 3

  정답 :

  ④

  문법을 살펴보면 왼편이 하나의 논터미널로 구성되었고
  오른편은 우선형 형태이다.
        S －－→  aA | bS
        A －－→  aS | bB
        B －－→  aB | bB | ε
  따라서 type 3 정규문법이다.

• 

  다음은 주어진 문법을 정규표현으로 변환하는 과정이다.
  다음 중 문법 G가 생성할 수 없는 것은?
  
  

  연습문제 설명

  G ＝ ({S, A, B}, {a, b}, P, S)
    P: S －－→  aA | bS
        A －－→  aS | bB
        B －－→  aB | b
  
    <풀이> 생성규칙을 정규표현 방정식으로 변환하면
        S ＝  aA ＋ bS         ------ ①
        A ＝  aS ＋ bB         ------ ②
        B ＝  aB ＋ b         ------ ③ 이다.
      ③번식에서
         B ＝   a^*b  ------------- ④
       ②식을 대입하여 ①식을 풀면
      S ＝   aaS ＋ abB ＋ bS
        ＝   aaS ＋ bS + abB
        ＝   ( aa+b )S + abB   ----- ⑤
      여기에 ④ 식을 대입하면 풀면
       S ＝  (aa ＋ b)^＊aba^＊b 가 된다.

  답을 체크하세요

  1. aba
  2. abab
  3. babb
  4. aaabb

  정답 :

  ①

  S ＝  (aa＋ b)^＊ aba^＊b 이므로
  abab, babb, aaabb 등이 생성될 수 있다.
  그러나 aba 는 생성되지 않는다.