형식 문법

위키백과 ― 우리 모두의 백과사전.

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

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

[편집] 생성 문법

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

1. $S \rightarrow aSb$

2. $S \rightarrow ba$

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

[편집] 정의

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

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

로 이루어진다.

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

오토마타 이론: 형식 언어 및 형식 문법
촘스키 위계	형식 문법	형식 언어	최소한의 자동장치
Type-0	(무제약)	순환 열거 언어	튜링 기계
	(무제약)	순환 언어	판정자
Type-1	문맥 의존 문법	문맥 의존 언어	선형유한 오토마타
Type-2	문맥 무관 문법	문맥 무관 언어	내리누름 오토마타
Type-3	정규 문법	정규 언어	유한 오토마타
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다.

분류: 형식 언어

See also ebooksgratis.com: no banners, no cookies, totally FREE.

형식 문법

위키백과 ― 우리 모두의 백과사전.

[편집] 생성 문법

[편집] 정의

Views

둘러보기

찾기

다른 언어