Grammer

○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