필기용 블로그

○Poisson process {N(t), t ≥ 0}

 ▶다음 조건들을 만족하는 Counting Process (주어진 시간 내에 일어난 사건의 수)

  ▷N(0) = 0

  ▷{N(t), t ≥ 0}

  ▷P(N(t + h) - N(t) = 1} = λh + o(h) (h : 작은 시간 / o(h) : 매우 작은 값들 - 무시 가능)

  ▷P(N(t + h) - N(t) ≥ 2} = o(h) - 2번이상 일어날 가능성 거의 없음.

 ▶N(t), t≥0이 Poisson process라면 (rate λ ＞ 0)

  ▷주어진 간격 t 내의 사건의 수 (N(t + h) - N(t))는 Poisson random variable이다. (mean = λt)

 ▶Interarrival and Waiting time distribution

  ▷T_n : (n-1)번째 사건과 n번째 사건 사이의 간격 (sequence of interarrival times)

  ▷T_n ~ Exp(λ) (mean 1/λ)

  ▷Waiting time S_n ~ Gamma(n, λ)

○Exponential distribution

 ▶Exponential Variable

 ▷Exponential은 Memoryless하다.

  ▷𝑃{𝑋 > 𝑠 + 𝑡 | 𝑋 > 𝑡} = 𝑃{𝑋 > 𝑠}

 ◎주문량에 따른 이익 비교

  ▷X : 고객의 요구 량, EXP(λ)

  ▷t : 재료 주문량

  ▷c : 재료 구입 비용 (c×t) / s : 판매가 (s×t)

 ▶Gamma(n, λ)

  ▷X₁, ...., X_n이 독립적이고 동일한 distrubuted exponential (평균 : 1/λ) 일때

  ▷X₁ + ... + X_n ~ Gamma(n, λ)가 성립한다.

  ▷증명

 ▶P{X₁ < X₂}

  ▷X₁ ~ Exp(λ₁) / X₂ ~ Exp(λ₂)

  ▷P{X₁ < X₂} = λ₁ / λ₁+λ₂

  ▷증명

 ▶P{min(X₁, ..., X_n) > x}

  ▷ = P{X_i > x (모든 i에 대해)}

  ▷ = e^∑_i (λ_i x)

  ◎Greedy Algorithm for the Assignment Problem

   ▷C_i,j : i사람을 j직업에 배치하는데 드는 비용

   ▷여러 사람이 같은 직업을 가질 수는 없다.

   ▷각 비용은 Exponential(1)을 따른다. (independent)

   ▷n명의 사람에게 n개의 직업을 배치할 때, 비용을 최소로 잡는 Algorithm

   ▶Greedy Algorithm 1

    ▷C_i : i번째 사람에 대한 비용

    ▷C_i1 : n개의 independent exponential의 minimum

    ▷E[C₁] = 1/n, E[C₂] = 1/(n-2), ...

    ▷E[C₁ + C₂ + ... + C_n] = 1/n + 1/(n-1) + ... + 1

   ▶Greedy Algorithm 2

    ▷C_i : 알고리즘으로 뽑은 i번째 사람-직업 짝의 비용

    ▷E[C₁] = 1/n^2 (전체 Matrix에서 최소 비용)

    ▷E[C₂] = E[C₁] + 1/(n-2)^2 (C₁의 행, 렬을 제외하고 최소 비용, 얼마나 더 초과하느냐?)

    ▷E[C_n] = E[C_n-1] + 1

    ▷E[C₁ + C₂ + ... + C_n] = 1/n + 1/(n-1) + ... + 1

●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