정규 문법
위키백과 ― 우리 모두의 백과사전.
정규 문법은 형식 문법의 일종으로, (N,Σ,P,S)에서 생성 규칙 P가
- A → a
- A → aB
- A → ε, ε는 길이가 0인 빈 문자열
으로만 구성되어 있거나,
- A → a
- A → Ba
- A → ε, ε는 길이가 0인 빈 문자열
으로만 구성되어 있는 것을 말한다. 이때 ,
이다. 이때 A → aB꼴로 구성된 언어를 우선형 문법, A → Ba 꼴로 구성된 언어를 좌선형 문법이라고 한다.
이 문법은 정규 언어를 완전히 표현하는 문법으로, 또한 유한 오토마타와 완전히 대응한다. 즉, 모든 정규 문법에대응하는 유한 오토마타가 적어도 하나 있고, 반대로 모든 유한 오토마타에 대응하는 정규 문법이 적어도 하나 존재한다. 또한 이 문법은 정규식과도 대응한다.
좌선형 문법으로 만들어지는 언어는 우선형 문법으로 만들 수 있다. 반대로 우선형 문법으로 만들어지는 언어는 좌선형 문법으로 만들 수 있다.
만약 생성 규칙에서 A → aB와 A → Ba 꼴이 같이 존재한다면 그 문법은 정규 문법이 아니라 선형 문법이라고 한다. 이 문법으로 만들어지는 언어는 정규 언어가 아닐 수도 있다. 예를 들어,
- S → aA
- A → Sb
- S → ε
는aibi의 문자열을 만들어내지만, 이것은 정규 언어에 속하지 않는다.
오토마타 이론: 형식 언어 및 형식 문법 | |||
---|---|---|---|
촘스키 위계 | 형식 문법 | 형식 언어 | 최소한의 자동장치 |
Type-0 | (무제약) | 순환 열거 언어 | 튜링 기계 |
(무제약) | 순환 언어 | 판정자 | |
Type-1 | 문맥 의존 문법 | 문맥 의존 언어 | 선형유한 오토마타 |
Type-2 | 문맥 무관 문법 | 문맥 무관 언어 | 내리누름 오토마타 |
Type-3 | 정규 문법 | 정규 언어 | 유한 오토마타 |
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다. |