Lec03. Lexical Analysis(2) (2주차 1강)

2주차 1강 - 9월 9일 월요일, Lexical Analysis

 

<개인 공부용으로 정리하는 것입니다. 정확한 내용은 본인이 공부하는 교재를 꼭 참고하시기 바랍니다.>

1. String Recognition using Finite Automata

• Finite Automata
  • 정의: yes or no를 return하는 string recognizer
    • 이 string에 accept 가능한가? 아닌가?를 판별한다.
  • 종류
    
    • Non-deterministic Finite Automata(NFA)
    • Deterministic Finite Automata(DFA)

 

2. Possibility of Correct String Recognition

• 문자열 s, 패턴 R
• 문자열 s가 어떤 Finite Automata에 속하는지 확인하고 싶다.즉, s가 L(R)에 존재하는지 확인하고자 한다.
• 패턴 R을 인식하는 Finite Automata를 찾고, L(R)과 L(FA)가 동일한지 확인해야 한다.
• 만약 L(R)!=L(FA)라면 올바르지 않은 문법을 유효하다고 인식하거나, 올바른 문법을 틀렸다고 인식할 수 있다.
• [질문] 그렇면, 주어진 R에 대해 L(R)=L(FA)인 FA가 존재하는가? 즉, 항상 올바른 result를 내는 lexer가 존재하는가?
  • [답] "그렇다" by. Kleene's Theorem
  • Kleene's Theroem: 모든 regex(정규언어)는 DFA와 NFA로 표현될 수 있다.
  • 따라서, 원하는 패턴을 정확하게 처리할 수 있는 FA가 존재함을 보장한다.
  • 정규식으로 정의된 언어는 항상 DFA나 NFA로 인식할 수 있으므로, 패턴 R을 처리하는 FA의 result는 항상 옳다.

3. Non-deterministic Finite Automata (NFA)

• 정의
  • Q: state의 유한 집합.
  • Σ : Alphabet. input symbol의 유한 집합. ε (빈 문자열)을 포함하지 않음.
  • q₀ : 초기 state(시작 state)
  • F: 최종 state(accepting state, 여기에 도달하면 이 string은 인식 가능한 문자열)
  • δ : 현재 상태와 입력 기호 (또는 ε)를 받아서 다음 가능한 상태들의 집합을 반환
    • 하나의 state에서 갈 수 있는 state가 여러 개임(NFA의 특징)
    • 2^Q는 상태 집합의 부분집합, NFA가 여러 상태로 전이할 수 있음을 나타냄
    • δ:Q×(Σ∪{ϵ})→2^Q

• 예제
  • δ(0, a) = {0, 1}
  • δ(current state, input symbol) = {possible next state}
  • 현재 state에서 input symbol을 받았을 때 갈 수 있는 다음 state

• 위 상태를 그래프로 표현하면 이렇게 볼 수 있음 (transition graph)

• 그래프를 transition table로도 표현할 수 있다.
  • state에서 symbol을 입력받았을 때 갈 수 있는 state를 표현한 것이다.
  • 만약 존재하지 않는다면 공집합으로 표시한다.

4. Strings Recognizable by NFA

• NFA로 판별될 수 잇는 string의 집합을 L(NFA)라고 한다.
• 예시에서 보이는 NFA는 abb로 끝나는 모든 string을 인식할 수 있다.

[예제] NFA를 보고 Regular Expression 표현하기

첫 번째, a 또는 b loop를 가진 final state 한 개로 구성됨 -> (a|b)*

두 번째, a 또는 b loop를 0 state에서 가지고 있으며, 마지막 문자가 a 또는 b가 되며 final state에 도달함 -> (a|b)*.(a|b)

첫 번째, a가 1개 이상인 문자열이거나, b가 1개 이상인 문자열 이거나 (a+|b+)

두 번째, a가 2의 배수로 반복됨, b가 2의 배수로 반복됨, b로 final state에 도달함 (aa)*(bb)*b

주어진 NFA가 string을 accept하는가 reject하는가

첫 번째, aabb (accept)

state 0에서 a를 받아 state0로 돌아옴, a를 받아 state1로 이동, b를 받아 state2로, b를 받아 state3으로(종료)

두 번째, aa (reject)

state 0에서 a를 받아 state0로, a를 받아 state 1로 -> final state 아님

state 0에서 a를 받아 state0로, a를 받아 state0로 -> final state 아님

 

5. Deterministic Finite Automata(DFA)

• 특징
  • ε 이동이 없음
  • 각 state에서 input symbol에 대해 unique한 next state가 존재함. (단 하나의 next state)
  • 각 입력에 대해 하나의 고유한 경로를 따르게 됨
• 정의 M=(Q,Σ,δ,q0​,F)
  • Q : 유한 상태 집합 (오토마타가 가질 수 있는 모든 상태의 집합)
  • Σ : 입력 기호 집합 (input alphabet)
  • δ : 전이 함수, transaction function, δ:Q×Σ→Q
    • 각 state의 input symbol에 대한 next state를 unique하게 결정
  • q0​ : 초기 상태로, q0∈Q
  • F : 최종 상태 집합으로, F⊆Q

[예제]

 

난 보통 풀 때 final state로 가는 흐름을 중심으로 본다 (왼쪽에서 오른쪽 순으로 보기)

1. state 0 -> 1 -> 2 -> 3으로 가는 경로에서 a b b가 존재한다 = string이 abb로 끝나야 한다

2. state 0에서 b loop가 존재함 -> b*를 인식할 수 있음

3. state 1에서 a loop가 존재함 -> a*를 인식할 수 있음

4. (a | b)* 후에 abb로 종료되는 형태의 string을 인식함 

5. (a | b)*abb

1. state 0 -> 1 -> 2 흐름 보면 ab, ab를 포함해야 함

2. final state에서 a,b loop -> (a|b)*를 accept

3. ab(a|b)*

 

1. state 0 -> 1-> 2 흐름, 01, 01을 포함해야 함

2. q0의 1 loop -> 1*

3. q1의 0 loop -> 0*

4. (0 | 1)*01

 

6. String Recognition using DFA

 

첫 번째, aabb

1. state 0 -> 1로 이동하며 a 인식

2. state 1 loop, a 인식

3. state 1->2, b 인식

4. state 2->3, b 인식

5. accept

 

두 번째, aa

1. state0->1, a 인식

2. state1 loop, a 인식

3. final state 도달 못함

4. reject

 

7. 왜 DFA를 쓰냐?

• NFA와 DFA 모두 문자열을 인식하는 도구, 그런데 lexer는 왜 DFA에 의존하는가?
• 초기 구성 단계
  • NFA: 정규식 크기만큼 시간 복잡도를 가짐. O(|r|)
    • 정규식에서 각 연산자와 피연산자를 NFA로 변환하는 과정이 간단함.
    • state 수는 정규식의 길이에 비례함
  • DFA(일반적인 경우): NFA를 만들고 DFA로 변환하며 오래 걸림 O(|r|^3)
    • NFA -> DFA는 subset struction 알고리즘 사용해서 가능한 state 집합 판별함
      
      • 각 집합에 대해 새로운 DFA state를 만들기 때문에 시간이 오래 걸림
  • DFA(최악의 경우): O(2^|r|)
    • NFA가 n개의 state 가짐, 해당 state로 만들 수 있는 모든 부분 집합 고려
      • 각 state를 넣거나 빼거나? -> 2^|r|
• 문자열 처리
  • NFA: O(|r| x |x|), 입력 문자열의 길이 x와 정규식의 크기를 곱함
  • DFA: 문자열의 길이에 비례, O(|x|), 각 문자에 대해 unique state만 존재함
• DFA는 초기 세팅은 오래 걸리지만, 문자열 처리 속도가 빨라 효율적임

 

8. 요약

• lexical pattern에 대해 어떻게 accept하고 reject하는지 알아봤음
  • NFA, DFA의 정의
  • NFA, DFA로 string을 어떻게 판별(recognize)하는가