Language Type

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