정규 문법 문서 원본 보기

{{위키데이터 속성 추적}}
'''정규 문법'''({{lang|en|regular grammar}})은 [[정규 언어]]를 기술하는 [[형식 문법]]이다. 정규 문법은 4-튜플 ''<N, Σ, P, S>''에서 생성 규칙 P가

# <math>A \,\to\, a</math>
# <math>A \,\to\, aB</math>
# <math>A \,\to\, \varepsilon</math> 
으로만 구성되어 있거나(우선형 문법),

# <math>A \,\to\, a</math>
# <math>A \,\to\, Ba</math>
# <math>A \,\to\, \varepsilon</math>
으로만 구성되어 있는 것(좌선형 문법)을 말한다. 이때 <math>A, B \in N</math>, <math>a \in \Sigma</math>이고 ε는 길이가 0인 문자열이다.

이 문법은 [[정규 언어]]를 완전히 표현하는 문법으로, 또한 [[유한 오토마타]]와 완전히 대응한다. 즉, 모든 정규 문법에 대응하는 유한 오토마타가 적어도 하나 있고, 반대로 모든 유한 오토마타에 대응하는 정규 문법이 적어도 하나 존재한다. 또한 이 문법은 [[정규식]]과도 대응한다.

좌선형 문법으로 만들어지는 언어는 우선형 문법으로 만들 수 있다. 반대로 우선형 문법으로 만들어지는 언어는 좌선형 문법으로 만들 수 있다.

만약 생성 규칙에서 <math>A \,\to\, aB</math>와 <math>A \,\to\, Ba</math> 꼴이 같이 존재한다면 그 문법은 정규 문법이 아니라 [[선형 문법]]이라고 한다. 이 문법으로 만들어지는 언어는 정규 언어가 아닐 수도 있다. 예를 들어,

# <math>S \,\to\, aA</math>
# <math>A \,\to\, Sb</math>
# <math>S \,\to\, \varepsilon</math>
는 <math>a^i b^i</math>의 문자열을 만들어내지만, 이것은 정규 언어에 속하지 않는다.

== 같이 보기 ==
* [[정규 표현식]]

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

{{전거 통제}}

[[분류:형식 언어]]