형식 문법

형식 문법(形式文法, formal grammar)은 형식 언어를 정의하는 방법으로, 유한개의 규칙을 통해 어떤 문자열이 특정 언어에 포함되는지를 판단하거나, 그 문법으로부터 어떤 문자열을 생성해 낼지를 정한다.

형식 문법은 그 문법으로부터 문자열들을 생산해 내는 생성 문법(生成文法, generative grammar)과, 문자열이 특정 언어에 포함되는지를 판단하는 해석 문법(解析文法, analytic grammar)으로 나눌 수 있다.

생성 문법은 특정 문자열에서부터 시작하여 여러 생성 규칙에 따라 문자열을 생성해낸다. 예를 들어, 다음의 규칙으로 구성된 문법이 있다고 할 때:

1. ${\displaystyle S\,\rightarrow \,aSb}$
2. ${\displaystyle S\,\rightarrow \,ba}$

${\displaystyle S}$로부터 시작하여 이 문법으로부터 생성되는 문자열은 ${\displaystyle ba,\,abab,\,aababb,\,aaababbb}$ 등이 있다. 예를 들어, ${\displaystyle aababb}$는 ${\displaystyle S\,\Rightarrow \,aSb\,\Rightarrow \,aaSbb\,\Rightarrow \,aababb}$와 같은 방법을 통해 생성해낼 수 있다.

일반적으로 가장 많이 사용하는 생성 문법의 정의는 다음과 같다. 생성 문법 ${\displaystyle G=(N,\Sigma ,P,S)}$는:

• 유한개의 중간 기호가 모인 집합 ${\displaystyle N}$
• 유한개의 말단 기호가 모인 집합 ${\displaystyle \Sigma }$
• 유한개의 생성 규칙이 모인 집합 ${\displaystyle P}$, 여기에서 생성 규칙은 ${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$의 꼴.
• 시작 기호 ${\displaystyle S\in N}$

로 이루어진다.

이때 ${\displaystyle {\boldsymbol {L}}(G)}$는 생성 문법 ${\displaystyle G}$로부터 만들어지는 모든 문자열의 집합으로 정의된다.

 이 부분의 본문은 촘스키 위계입니다.

촘스키 위계에서 형식 문법은 생성 문법의 제약의 양에 따라 무제약 문법부터 시작하여 0 ~ 3 타입으로 분류된다. 이는 노엄 촘스키가 1956년 생성 문법을 체계적으로 정의하면서 구성한 것인데, 재귀 문법을 규정하고 있지 않다.

• 형식 언어
• 생성문법
• 문자열