Context Free Grammar
문법 G = (V, T, S, P) 에서 모든 생성규칙이
A → x
의 형태를 가지면 G 를 문맥-자유 문법 (context-free
grammar : CFG) 이라고 한다. 여기서 A ∈ V 이고, x ∈ (V∪T)* 이다.
또한
언어 L 에 대해서 L = L(G) 를 만족하는 문맥-자유 문법 G 가 존재하고 오직 그럴 때에만
L 을 문맥-자유 언어 (context-free language : CFL) 라고 한다.
위의 정의에 의하면 모든 정규 문법은 문맥-자유 문법이 되며, 따라서 정규 언어는 문맥-자유 언어임을 알 수 있다. 그러나, L = {anbn : n ≥ 0} 와 같은 예로부터 알고 있듯이, 정규 언어가 아닌 언어가 존재한다. 따라서 정규 언어군은 문맥-자유 언어군의 진부분 집합임을 알 수 있다. .......... 문맥-자유 문법이란 이름은 문장 형태에 있는 임의의 변수는 그 변수를 좌변으로 갖는 생성규칙에 의하여 치환될 수 있다는 사실로부터 유래된다. 이러한 치환은 문장 형태(문장)에 있는 나머지 심볼들과는 상관없이 이루어진다. 이런 특징은 생성규칙의 좌변에 변수 하나만이 허용되기 때문에 얻어지는 결과이다............... (Peter Linz 2001)
문맥-자유 언어는 프로그래밍 언어에 적용이 되기 때문에, 이에 관한 연구는 아마도 형식언어 (Formal Language) 이론의 가장 중요한 부분일 것이다. 실제의 프로그래밍 언어는 문맥-자유 언어로 잘 표현될 수 있는 여러 특성들을 가지고 있다. 형식 언어 이론에서 밝혀진 문맥-자유 언어에 대한 결과들은 프로그래밍 언어의 설계에서 뿐만 아니라 효율적인 컴파일러 작성에 중요하게 사용된다
term :
문맥자유 문법 (Context Free Grammar) 문맥인식 문법 (Context Sensitive Grammar) 언어학 (linguistics) 인공지능 (Artificial Intelligence) 촘스키 계층 (Chomsky Hierarchy) 계산가능성 이론 (Computability Theory) 문맥 (Context) 지식 (Knowledge) 형식언어 (Formal Language)
site :
Wikipedia : Context-free grammar
paper :