형식 문법 문서 원본 보기

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

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

== 생성 문법 ==

생성 문법은 특정 문자열에서부터 시작하여 여러 생성 규칙에 따라 문자열을 생성해낸다. 예를 들어, 다음의 규칙으로 구성된 문법이 있다고 할 때:
:# <math>S \,\rightarrow\, aSb</math>
:# <math>S \,\rightarrow\, ba</math>
<math>S</math>로부터 시작하여 이 문법으로부터 생성되는 문자열은 <math>ba,\, abab,\, aababb,\, aaababbb</math> 등이 있다. 예를 들어, <math>aababb</math>는 <math>S \,\Rightarrow\, aSb \,\Rightarrow\, aaSbb \,\Rightarrow\, aababb</math>와 같은 방법을 통해 생성해낼 수 있다.

=== 정의 ===
일반적으로 가장 많이 사용하는 생성 문법의 정의는 다음과 같다. 생성 문법 <math>G = (N, \Sigma, P, S)</math>는:
* 유한개의 중간 기호가 모인 집합 <math>N</math>
* 유한개의 말단 기호가 모인 집합 <math>\Sigma</math>
* 유한개의 생성 규칙이 모인 집합 <math>P</math>, 여기에서 생성 규칙은 <math>(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}</math>의 꼴.
* 시작 기호 <math>S \in N</math>
로 이루어진다.

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

== 촘스키 위계 ==
{{본문|촘스키 위계}}

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

== 같이 보기 ==
* [[형식 언어]]
* [[생성문법]]
* [[문자열]]

{{형식 언어 및 형식 문법}}

{{전거 통제}}

[[분류:형식 언어]]
[[분류:문법]]
[[분류:수리논리학]]
[[분류:통사론]]
[[분류:오토마타 이론]]