정규 문법

정규 문법(regular grammar)은 정규 언어를 기술하는 형식 문법이다. 정규 문법은 4-튜플 <N, Σ, P, S>에서 생성 규칙 P가

1. ${\displaystyle A\,\to \,a}$
2. ${\displaystyle A\,\to \,aB}$
3. ${\displaystyle A\,\to \,\varepsilon }$

으로만 구성되어 있거나(우선형 문법),

1. ${\displaystyle A\,\to \,a}$
2. ${\displaystyle A\,\to \,Ba}$
3. ${\displaystyle A\,\to \,\varepsilon }$

으로만 구성되어 있는 것(좌선형 문법)을 말한다. 이때 ${\displaystyle A,B\in N}$, ${\displaystyle a\in \Sigma }$이고 ε는 길이가 0인 문자열이다.

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

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

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

1. ${\displaystyle S\,\to \,aA}$
2. ${\displaystyle A\,\to \,Sb}$
3. ${\displaystyle S\,\to \,\varepsilon }$

는 ${\displaystyle a^{i}b^{i}}$의 문자열을 만들어내지만, 이것은 정규 언어에 속하지 않는다.

• 정규 표현식