Lec04. Lexical Analysis (3) (2주차 2강, 4주차 1강/2강)

수업: 9월 11일 2주차 2강 + 9월 23일 4주차 1강 + 9월 25일 4주차 2강 (3주차 1강, 2강은 추석으로 휴강)

* 본 자료는 제 개인 공부용으로 정리한 것입니다. 정확한 자료는 꼭 본인이 공부하는 교재를 참고하시길 바랍니다.

 

---

9월 11일 2주차 2강

1. Construction of DFA

• Methodology: lexical specification을 동일한 string recognizer로 변환한다
  
  • Regular Expression, 정규 표현식: 특정 패턴의 문자열을 정의
  • Lexical Specification: 특정 언어에서 허용되는 문자 패턴을 정의
  • String Recognizer: 입력된 문자열이 주어진 규칙(RE)과 일치하는지 판별
  • DFA: state와 transition을 사용해 문자열 처리 -> 주어진 규칙을 준수하는가?
• 주어진 문자열 패턴(RE)를 판별에 사용할 수 있는 형태(DFA)로 변환한다는 의미인 것 같음
  • RE -> NFA -> DFA 순서로 변환한다
• RE -> NFA: Thompson's 알고리즘, NFA -> DFA: subset construction
• 각 변환의 정확성을 판단하는 기준은 semantic equivalence(언어적 의미의 등가성)
  • L(RE)=L(NFA), L(NFA)=L(DFA)를 통해 각 변환이 올바른지를 확인한다.
  • 변환이 되어도 언어의 expression이 변하지 않아야 한다는 의미.

2. Thompson's construction: RE to NFA

변환에 위 두 transfomration rule을 사용한다.

2.1. Basic Rules

가장 기본적인 정규 표현식을 NFA로 변환한다. 문자 하나 또는 빈 문자열을 NFA로 변환하는 방법이다.

2.2. Inductive Rules

복잡한 정규 표현식을 만들기 위해 작은 부분 표현식의 NFA를 결합해서 큰 NFA를 구성한다.

• R = R₁ | R₂
  • 1단계: R1과 R2 각각의 NFA를 만든다.
  • 2단계: ε-transitions를 사용해 두 개의 NFA를 연결한다. R1 또는 R2를 선택해 final state에 도달
  • L(NFA) = L(R₁) ∪ L(R₂)
    • start에서 시작한 어떤 path이든 NFA_R1(L(R1)) 또는 NFA_R2(L(R2)) 둘 중 하나를 통과함
    • 문자열은 ε-transitions에 의해 변형되지 않는다

• R = R₁ · R₂
  • 1단계: R1과 R2 각각의 NFA를 만든다.
  • 2단계: ε-transitions를 사용해 연결한다. R1에서 R2로 ε-transitions를 통해 이동
  • x ∈ L(R₁) ∧ y ∈ L(R₂), x는 R1에서 인식되는 문자열, y는 R2에서 인식되는 문자열
  • 두 문자열이 연결된(AND) 형태를 L(NFA)에서 수용한다

• R = R₁*
  • 1단계: R1의 NFA를 만든다
  • 2단계: start에서 ε-transitions로 final로 진입, final에서 ε-transitions로 start로 되돌아감
  • L(NFA) = {ε} ∪ (L(R₁))⁺ = (L(R₁))*
    • {ε}: ε는 빈 문자열을 의미하며, R₁이 0회 반복될 때 수용하는 경우
    • (L(R₁))⁺: R₁의 언어가 1회 이상 반복되는 경우
    • R1이 0회 이상 반복되는 경우를 표현

2.3. Exercises

예제 풀이(정답은 알아서 풀어보라고 하셔서 내가 틀렸을수도 있음)

 

3. NFA to DFA: subset construction

• NFA를 DFA로 바꾸는 방법

3.1. Subset Construction

• NFA에서 non-deterministic choice를 제거한다.
  • string에 영향을 주지 않는 state를 합친다.
  • 이미지 예시에서 보면 0->1, 0->3은 input값이 epsilon이다.
  • epsilon은 빈 문자열이므로 {0,1,3}을 한  state로 합칠 수 있다.

3.2. Epsilon-Closure

예시와 함께 이해해 보자

• Epsilon-Closure란... symbol 입력 없이 I에서 시작해서 도달할 수 있는 state의 set을 말한다.
• 어떤 state에서 출발해서 epsilon으로 연결된 state를 모두 탐색하면 된다.
• 유념해야 할 점은, 어떤 state에서 다른 state에 도달했을 때, 그 state에서도 epsilon으로 연결된 state들도 포함해야 한다.
  • BFS 마냥 전부 둘려봐야 함.
• state1에서 출발, 1->2->3, 2->9, 3->4, 3->6 {1,2,3,4,6,9}
• state 5에서 출발, 5->8->9, 8->3, 3->4, 3->6 {3,4,5,6,8,9}

Step by step 예시

• 1단계: ε-closure({0}): state 0에서 출발
  • state 0에 a가 들어왔을 경우, 0->1->2->3, 2->9, 3->4, 3->6 {1,2,3,4,6,9}
  • state 0에 b가 들어왔을 경우, 갈 수 있는 곳 없음. 공집합(dead state로 이동)
  • state 0에 c가 들어왔을 경우, 갈 수 있는 곳 없음. 공집합(dead state로 이동)
  • 따라서, state {0}에서 state {1,2,3,4,6,9}로 이동하기 위해 a input이 필요

• 2단계: ε-closure({1,2,3,4,6,9})에서 출발
  • a가 들어왔을 경우, a가 input인 transition이 없음, 공집합(dead state)
  • b가 들어왔을 경우, 4에서 5로 진입하는 transition의 input이 b
    • 5->8->9, 8->3, 3->4, 3->6 {3,4,5,6,8,9}
  • c가 들어왔을 경우, 6에서 7로 진입하는 transition의 input이 c
    • 7->8->9, 8->3->4, 3->6 {3,4,6,7,8,9}

• 3단계: ε-closure({3,4,5,6,8,9})에서 출발
  • a가 들어왔을 경우, a가 input인  transition 없음, 공집합(dead state)
  • b가 들어왔을 경우, 4에서 5로 진입하는 transition의 input이 b
    • 5->8->9, 8->3, 3->4, 3->6 {3,4,5,6,8,9}
  • c가 들어왔을 경우, 6에서 7로 진입하는 transition의 input이 c
    • 7->8->9, 8->3->4, 3->6 {3,4,6,7,8,9}

• 4단계: ε-closure({3,4,6,7,8,9})에서 출발
  • a가 들어왔을 경우, a가 input인  transition 없음, 공집합(dead state)
  • b가 들어왔을 경우, 4에서 5로 진입하는 transition의 input이 b
    • 5->8->9, 8->3, 3->4, 3->6 {3,4,5,6,8,9}
  • c가 들어왔을 경우, 6에서 7로 진입하는 transition의 input이 c
    • 7->8->9, 8->3->4, 3->6 {3,4,6,7,8,9}

---

9월 23일 4주차 1강 + 9월 25일 4주차 2강

3.3 Subset Construction Algorithm

• 입력:
  • NFA의 구성 요소:
    • N: state 집합
    • Σ: input symbol 집합
    • δ_N: transition function
    • n₀: start state
    • N_A: final state
• 출력:
  • DFA의 구성 요소:
    • D: state 집합
    • Σ: input symbol 집합
    • δ_D: transition function
    • d₀: start state
    • D_A: final state
• d₀ ← ε-closure({n₀}): n₀에서 ε-transition으로 도달할 수 있는 모든 상태들의 집합, DFA의 start state
• D ← {d₀}: DFA의 state 집합에 시작 상태 d₀를 추가
• W ← {d₀}: W는 처리해야 할 DFA state의 집합, d0를 추가
• while W ≠ ∅ do: W가 빌 때까지 반복
  • q ← remove q from W: W에서 state q를 하나 제거
  • for x ∈ Σ do: input symbol x에 대해 반복
    • t ← ε-closure(∪_{s∈q} δ_N(s, x)):
      • q에 있는 state s에서 x에 대한 transition을 모두 구해서, ε-transition를 통해 도달할 수 있는 state의 집합 t
    • D ← D ∪ {t}: t를 D에 추가
    • δ_D(q, x) ← t: DFA의 transition function에 q에서 input x로 이동했을 때 t로 transition 됨을 기록
    • if t has not been added to W before then: t가 아직 W에 없으면 추가
• D_A ← {q | q ∈ D, q ∩ N_A ≠ ∅}: NFA의 final state가 포함된 DFA state를 final state로 지정
• return (D, Σ, δ_D, d₀, D_A): DFA 정의된 내용 반환
• 참고: t가 공집합인 경우 W에 t를 추가할 필요가 없어서 skip.

 

[Again] Step by step 예시 -> 방금 배운 algorithm 순서에 따라

 

• 1단계: initial state 정의, DFA state 집합에 {0} 추가, process할 집합에 {0} 추가

• 2단계: state {0}에서 a, b, c를 입력받았을 때 도달 가능한 state, DFA state에 해당 set추가, W에도 추가

• 3단계: W set에서 state {1,2,3,4,6,9} pop함, a,b,c 입력 시 도달 가능한 state D와 W 추가

• 4단계: W에서 {3,4,5,6,8,9} pop, a/b/c 입력 시 도달 가능한 state, D와 W에 이미 있어서 추가 안함

• 5단계: W에서 {3,4,6,7,8,9} pop, a/b/c 입력 시 도달 가능한 state, D, W에 이미 있어서 추가 안함

• 종료단계: W에 아무것도 안남음. 종료
  • accepting state가 NFA에서 9이므로, 9를 포함한 DFA state는 accepting state가 된다

3.4 Algorithm for Computing Epsilon-Closures

• ε-closure(I): 주어진 상태 집합 I에서 ε-transition를 통해 도달할 수 있는 모든 state들의 집합
• T = ε-closure(I): I ∪ ⋃_{s∈T} δ(s, ε) ⊆ T 를 만족하는 가장 작은 집합
  • I와 T에 속한 state들 s에서 ε-transition를 통해 도달할 수 있는 모든 state 포함하는 가장 작은 집합 T
• F(X) ⊆ X, F(X) =   I ∪ ⋃_{s∈X} δ(s, ε)
  • F(X)는 state S에서 ε-transition 를 통해 도달할 수 있는 모든 state를 조합한 집합
  • 이를 만족하는 가장 작은 집합이 T =  F의 least fixed point = fixF
• Least Fixed Point
  • F를 계속 적용해도 더 이상 값이 변하지 않는 가장 작은 해

3.5 Why Smallest Solution?

왜 가장 작은 해를 구해야 하는가?

• ε-closure({1}) = {1,2,3,4,6,9} 유일한 해는 아니다
• X={0,1,2,3,4,6,7,8,9} 이 역시 F(X) ⊆ X를 만족하는 해가 될 수 있음
  • 왜냐? <- 이게 진짜 이해가 안돼서 계속 찾아봤는데 일단 지금 내린 결론은 이러함
    • ε-closure의 정의: ε-transition으로 도달할 수 있는 모든 state의 집합이라고 할 경우
    • 일단 모든 state들이 ε-transition을 가지고 있긴 하니까 모든 state의 set도 solution이 될 수 있는 거
    • 그럼 이 과정에서... 특정 state에서 ε-transition만으로 도달할 수 없는 state도 포함될 수 있음
    • 그래서, 이런 over set이 만들어지는 문제를 막기 위해서 엄밀하게 smallest set을 만들어야 됨
  • 근데 내 의문!!! ε-closure 정의 자체가 특정 state I에서 ε-transition으로만 도달할 수 있는 state의 집합 아님?
    • 교수님께 물어보고 추가하겠음;
• 문제점: 잘못된 lexeme을 받아들일 수 있음 -> (7,8)이 추가되면 c를 추가로 받게 됨
  • 그래서 least fixed point 구하는 게 중요!
  • smallest solution을 구해야 가장 정확한 해를 구함(새로운 state 추가가 안되면서도, 불필요한 state가 없는)

3.6. Fixed Point Iteration

• T를 처음에 공집합으로 설정
• 반복문
  • T'에 T의 현재 상태 저장
  • T에 T의 현재 상태와 T의 현재 상태를 F에 적용한 결과의 합집합을 T에 저장
  • T와 T'이 같아지면 멈춤
• T를 공집합으로 초기화한 이후에 T 범위 내에서 F 함수를 반복 수행

• 0단계: T'=T현재(공집합), T=T의 현재와 {1}에서 입실론만으로 갈 수 있는 state 추가 = 2 추가
• 1단계: T'={1,2}, {1,2}에서 입실론만으로 갈 수 있는 state 추가 = 3, 9 추가
• 2단계: T'={1,2,3,9}, {1,2,3,9}에서 입실론으로 갈 수 있는 state 추가 = 4, 6 추가
• 3단계: T'={1,2,3,4,6,9}, {1,2,3,4,6,9}에서 입실론으로 갈 수 있는 state 추가 = 더 없음! T=T' 정지

• 왜 T의 결과가 least solution인가?
  • T는 공집합에서 출발해서, 각 step마다 추가될 수 있는 가장 최소만을 추가하기 때문
• T가 수렴하는가? 왜 loop가 종료되는가?
  • T는 finite set이다. 무한히 커질 수 없다. fixed point에 도달하면 repeat이 종료한다.
  • T가 수렴하는 이유는 finite space에서 계속 확장되다가(줄어들지 않음) fixed point에 도달하기 때문이다.

4. 요약

• string recognizre 문자열 판별기 DFA 만들기
  • RE -> NFA: 톰슨 construction, base case와 inductive case 두 가지 사용
  • NFA->DFA: 부분집합 construction
    • 핵심: NFA에서 비결정적인 transition 제거
    • 모든 transition이 유일하게 만들기 위해 각 state에서 가능한 모든 input symbol을 테스트 해야함
    • input symbol에 의한 도달 가능성을 테스트할 때는 ε-closure를 사용한다
  • 다음시간: OCaml 각오해라.

끝~~~

이거 뭔 정리가 1달 걸린 거 같네요

취준이 너무 빡세서 중간고사 공부 미룬이 됨

 

노동요: 좋아하는 유튜버 영상, 리믹스 음악들, 가끔 클래식

요즘 스즈키 4권 곡들이 좋음... 역시 돌고 돌아 근본으로