필기용 블로그

●Language Types

 ▷컴퓨터에서 처리 가능한 4가지 Language

 ▷FA, Reguar Grammer, Regular Expression -> Regular Language

○Context-free Language

 ▶Context-Free Grammar

  ▶G = (V, Σ, S, P)

   ▷Production rule (x → y) 제약 : A → y ( A ∈ V, y ∈ (V ∪ Σ)* )

 ▶PushDown Automata (Stack Automata)

  ▶M = (Q, Σ, Γ, Δ, q_o, F)

   ▷Q : a set of finitee states

   ▷Σ : an alphabet

   ▷Γ : a stack alphabet - top(start symbool = #)

   ▷Δ : a subset of the transition relation

    ▷(Q × (Σ∪{λ}) × (Γ∪{λ})) × (Q × Γ*)

   ▷q_0 : a start (initial) state

   ▷F : a set of final states (F ⊆ Q)

  ▶FA vs PDA

  ◎PDA Example

○Context-Sensitive Language

 ▶Context-Sensitive Grammar

  ▷Production rule (x → y) 제약 : ||x|| ≤ ||y||

  ▷x ∈ ((V ∪ Σ)* V (V ∪ Σ)*), y ∈ (V ∪ Σ)*

  ▶Language of N-TM

   ▷Cotext-Sensitive Language (L)에 대해 L(N) = L 인 N(Non-deterministic Turing machine)이 존재한다.

 ▶Non-deterministic TM

  ▶N = (Q, Σ, Γ, δ, q_o, H)

   ▷Q : a set of finitee states

   ▷Σ : an alphabet

   ▷Γ : a tape alphabet - top(start symbool = #)

   ▷Δ : a subset of the transition relation

    ▷((Q - H) × Γ) × (Q × Γ × {L,R,S})

   ▷q_0 : a start (initial) state

   ▷H : a set of final states (F ⊆ Q)

○Recursively Enumerable Language

 ▶Language of TM

  ▷Recursively Enumerable Language (L)에 대해 L(T) = L 인 T(Turing machine)이 존재한다.

 ▶Turing Machine

  ▶T = (Q, Σ, Γ, δ, q_o, H)

   ▷Q : a set of finitee states

   ▷Σ : an alphabet

   ▷Γ : a tape alphabet - top(start symbool = #)

   ▷δ : a subset of the transition relation

    ▷(Q - H) × Γ → Q × Γ × {L,R,S}

   ▷q_0 : a start (initial) state

   ▷H : a set of final states (F ⊆ Q)

  ▶TM Operation

   ▷deterministic machine이다.

   ▷L : Left / R : Right / S : Staying

   ▷모든 input symbol을 읽고도 동작가능하다. -> 언제 끝나는지 알 수 없음

   ▷halt state - Machie 정지

  ▶TM Configuration

   ▷(q, u a v)

    ▷q : 현재 상태

    ▷a : Tape-head의 Symbol

    ▷u : Tape head 왼쪽 String

    ▷u : Tape head 오른쪽 String

    ◎0^n 1^n (1^n) 찾기

○Grammer

 ▶G = (V, Σ, S, P)

  ▷V : a finite set of variables

  ▷Σ : alphabet

  ▷S : a start variable (S ∈ V)

  ▷P : a set of production rules

   ▶production ruel : x -> y

    ▷x ∈ (V ∪ Σ)* V (V ∪ Σ)*

    ▷y ∈ (V ∪ Σ)*

 ▶Language of Grammer ( L(G) )

  ▷Grammer로부터 파생된 Language

  ▷L(G) = { ω ∈ Σ* | S =>* ω }

  ▷=>* : k-times derivation

   ▷production rule을 k번 적용한 것.

 ◎Example

 ▶Regular Grammer

  ▷일반적인 Grammer에서 production rule에 제한이 걸린 것,

  ▶A, B ∈ V, ω ∈ Σ*일때, 다음의 rule만 허용한다.

   ▷A → ωB

   ▷A → ω

○Conversion

 ▶Language Conversions

 ▶RG → NFA

  ▷1. 각 Variable을 state로 처리함 (Start Variable = Start State)

  ▷2. 각 Production rule을 transition으로 처리함.

  ▷3. 필요에 따라 추가적인 State가 필요할 수 있음. (2 번 이상의 transition이 필요한 경우)

 ◎Regular grammer -> NFA Example

 ▶DFA → Regular Grammar

  ▷1. Dead State는 고려하지 않음.

  ▷2. 각 State를 Variable으로 설정. (Start State = Start Variable)

  ▷3. 각 transition을 Production rule로 설정

  ▷4. Final State의 경우 Production rule에 λ 추가.

 ◎DFA -> Regular grammar Example

○DFA from NFA

 ▷Set of L(M_DFA) ⊆ Set of L(M_NFA)

  ▷DFA는 NFA의 일종이다.

 ▷어느 한 NFA가 있으면 L(M_DFA) = L(M_NFA)인 DFA가 존재한다.

 ▶DFA - derivation from NFA

  ▷DFA -> D = (Q_D, Σ, δ, S_0, F_D)

  ▷NFA -> N = (Q_N, Σ, Δ, q_0, F_N)

  ▷1. Start State에 대한 λ-Closure 구하기 -> S_0

  ▷2. S_0에 대한 Reachable State Set -> S_1, S_2, ... (Set이 다르면 State도 다르다.)

  ▷3. 이전 State에 대한 Reachable State. -> S_n ...

  ▷4. NFA의 Final State를 포함하는 Set을 의미하는 State -> DFA의 Final State

○NFA from Regular Expression

 ▷Regular Expression에 대해 이를 의미하는 NFA가 존재한다.

 ▶Tompson's Algorithm

  ▷다음 NFA의 Recursive Contruction을 이용해서 Regular Expression을 표현할 수 있다.

  ▷State가 많아지지만, 매우 쉽게 만들 수 있다.

  ▶속성

   ▷Number of states ≤ 2×number of steps

   ▷N은 단 하나의 Start State와 Final State를 가진다. (Final State 에서는 나가는 State가 없다.

   ▷하나의 Outgoing edge를 가지거나, 최대 2개의 Outgoing λ-edges르 가진다.

◎(0 + 11)*

○Regular Expression from DFA

 ▷Language of DFA를 의미하는 Regular Expression이 존재한다.

 ▶Algorithm

  ▷DFA M = ( {q_1, q_2, ... , q_n}, Σ, δ, q_1, F)

  ▷R_ij^k : k보다 높은 State를 거치지 않고 q_i에서 q_j로 가는 String (도착은 OK)

  ▷L(M) = ∪_q_final∈F R_1f^n

○Non-determinstic Finite Automata

 ▶다음과 같은 5개의 요소들로 구성된 FSM (N = (Q, Σ, Δ, q₀, F))

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷Δ: Q×(Σ∪{λ})×Q - transition relation의 subset -> 라벨이 있는 directed edge

  ▷q₀: start state (q0 ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▷input character에 대해 하나 이상의 transition이 존재한다.

  ▷deterministic : 각 input에 대해 단 하나의 transition

 ▷λ-transition이 가능하다.

 ▷Final State에 도착하는 하나 이상의 길이 있다 -> Acceptable String

 ▶Transition function (Δ_f)

  ▷Transition relation을 Function으로 취급한 것

  ▷Δ_f : Q x ( Σ ∪ {λ} ) -> ρ(Q)

   ▷ρ(Q) : power set of Q

 ▶Extended Transition Function (Δ_s)

  ▷Transition relation의 집합

  ▷Δ_s = ρ(Q) x ( Σ ∪ {λ} ) -> ρ(Q)

  ▷Δ_s(P, a) = ∪_q∈p Δ_f(q,a)

 ▶λ-Closure ( E(q) / E_s(P) )

  ▷E(q) : 어떤 Symbol도 읽지 않고 도달 가능한 State들의 집합

  ▷원래 State + λ를 통해 이동가능한 State

  ▷E_s(P) : ∪_q∈P E(q)

 ▶Reachable State Function ( Δ^*(q, s) )

  ▷State q에서 String w을 읽었을 때 도달 가능한 State set

  ▷NFA를 해석하는 방법. (Update)

  ▷Δ^* : Q × Σ^* -> ρ(Q)

 ▶NFA Language

  ▷해당 NFA에서 Accepted되는 Language들

  ▷Δ^*(q₀, w)가 하나 이상의 Final State를 가진다.

 ▶NFA Design

  ▷일반적으로 DFA Design보다 쉽다.

 ◎Regex (010+01)* 허용하는 String

 ◎Regex (0+1)*1(0+1) 허용하는 String

○Deterministic Finite Automata

 ▶다음과 같은 5개의 요소들로 구성된 FSM (M = (Q, Σ, δ, q₀, F))

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q₀: start state (q₀ ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▶Machine-Oriented Viewpoint

  ▷기계로 생각해 보는 DFA - cell들이 있는 input tape, read-only head, FA controller

  ▷메모리가 없음.

  ▷head는 가장 왼쪽(start state)에서 부터 오른쪽으로 움직임

  ▷δ(current state, tape symbol) -> next state

 ▶configuration (상황)

  ▷QΣ*

   ▷Q: 현재 State

   ▷Σ*: 아직 남아있는 input string

  ▶configuration sequence (px ┣ qy)

   ▷x = ay이고, δ(p, a) = q일 때. (a ∈ Σ)

   ▷px에서 qy으로 configuration이 transition 가능함.

   ▶px ┣^k qy

    ▷px에서 k-steps 이후 qy로 transition함.

    ▷px ┣ rz, rz ┣^k-1 qy

    ▷┣⁺ ≡ ┣^k (k ≥ 1) : transitve closure

    ▷┣^* ≡┣^k (k ≥ 0), 자기 자신도 포함. : reflexive transitive closure

    ▷┣⁺이 가능하면, ┣^*도 가능하다.

 ▶Accepted Language (L(M))

  ▷M = (Q, Σ, δ, S, F)에 대해서

  ▷Sx ┣^* fλ가 성립하는 x (x ∈ Σ^*, f ∈ F)

  ▷DFA Language: 어떤 DFA에 대해 Accepted Language인 L

 ▶Equivalence of DFA

  ▷DFA M₁, M₂에 대해서

  ▷L(M₁) = L(M₂)이면, M₁과 M₂는 equivalent하다.

 ▶DFA 설계

  ▷1. 기억해야할 정보 결정, State로 표현

  ▷2. Input마다 State transition을 결정.

  ◎1이 짝수개 있는 String (Σ = {0, 1})

  ◎Substring 0101을 가진 String (Σ = {0, 1})

   ▷0101을 찾는다면 Final State에서 빠져나가지 않는다.

  ◎Substring 0101을 가지지 않은 String (Σ = {0, 1})

   ▷Dead State: 들어간다면, Final State로 갈 수 없는 State

  ◎L( (010+01)* )

○Mealy vs Moore

 ▶Moore: M = (Q, Σ, δ, q_0, F)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨

  ▷δ: Q×Σ → Q인 transition function -> 라벨이 있는 directed edge

  ▷q_0: start state (q0 ∈ Q) -> 라벨이 없는 directed edge가 가리키는 원(state)

  ▷F: final states set(F ⊆ Q) -> 선이 2개인 원

 ▶Mealy: M = (Q, Σ, Γ, δ, γ)

  ▷Q: state symbols의 알파벳 -> 원

  ▷Σ: input symbols의 알파벳 -> 라벨 (앞)

  ▷Γ: output symbols의 앞바벳 -> 라벨 (뒤)

  ▷δ: Q×Σ → Q인 next state function -> 라벨이 있는 directed edge

  ▷γ: Q×Σ → γ인 output function