문맥 의존 문법

문맥 의존 문법(文脈依存文法, Context-sensitive grammar, CSG), 문맥 민감 문법은 형식 문법의 한 종류로, 생성규칙에서 시작 부분과 끝부분을 나타내는 것을 포함하는 부분이다.

 정의 
형식 문법 G = (N, Σ, P, S) (다음의 정의와 같다. G = (V, T, P, S), N/V는 비 말단 변수, Σ/T는 말단) 은 P의 모든 문법이 αAβ → αγβ 일 때 문맥 의존이다.

단, A ∈ N (A는 하나의 비말단), α,β ∈ (N U Σ)* ( α 와 β는 비말단과 말단 기호의 문자열) , γ ∈ (N U Σ)+ (γ는 비말단과 말단 기호로 된 길이가 0이 아닌 문자열)이다.

 예 
 1.         S      →      a  B  C 2.   S  →  a  S  B  C 3.  C  B  →  C  Z 4.  C  Z  →  W  Z 5.  W  Z  →  W  C 6.  W  C  →  B  C 7.  a  B  →  a  b 8.  b  B  →  b  b 9.  b  C  →  b  c10.  c  C  →  c  c

 같이 보기 
 촘스키 위계

분류:형식 언어