●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) 찾기
