정규 문법(regular grammar)은 계산 이론과 형식 언어 이론에서 정규 언어(regular language)를 기술하는 형식 문법(formal grammar)이다. 촘스키 위계(Chomsky hierarchy)에서 3형 문법(Type-3 grammar)에 해당하며, 정규 언어를 완전히 표현할 수 있는 문법으로 유한 오토마타(finite automata) 및 정규 표현(regular expression)과 상호 대응 관계에 있다.
정의
정규 문법은 4-튜플 ⟨N, Σ, P, S⟩로 정의된다.
- N: 비말단(non-terminal) 기호의 유한 집합
- Σ: 말단(terminal) 기호의 유한 집합 (알파벳)
- P: 생성 규칙(production rule)의 유한 집합
- S: 시작 기호 (S ∈ N)
정규 문법은 생성 규칙 P의 형태에 따라 우선형 문법(right-regular grammar)과 좌선형 문법(left-regular grammar)으로 나뉜다. 두 형식의 규칙을 혼합해서 사용할 수 없으며, 혼합할 경우 선형 문법(linear grammar)이 되어 정규 언어가 아닌 언어를 생성할 수 있다.
우선형 문법 (Right-Regular Grammar)
모든 생성 규칙이 다음 형태 중 하나로만 구성된다.
- A → a (비말단 기호 A가 말단 기호 a 하나로 변환)
- A → aB (비말단 기호 A가 말단 기호 a 뒤에 비말단 기호 B가 오는 형태로 변환)
- A → ε (비말단 기호 A가 빈 문자열 ε로 변환)
여기서 A, B ∈ N이고 a ∈ Σ이며, ε는 길이가 0인 문자열을 의미한다.
좌선형 문법 (Left-Regular Grammar)
모든 생성 규칙이 다음 형태 중 하나로만 구성된다.
- A → a
- A → Ba (비말단 기호 A가 비말단 기호 B 뒤에 말단 기호 a가 오는 형태로 변환)
- A → ε
확장 정규 문법 (Extended Regular Grammar)
일부 교재에서는 더 일반화된 형태의 확장 정규 문법을 사용하기도 한다. 확장 우선형 문법의 규칙은 다음과 같다.
- A → w (A는 비말단, w는 말단 문자열 Σ*)
- A → wB (A, B는 비말단, w는 Σ*)
확장 좌선형 문법의 규칙은 다음과 같다.
- A → w
- A → Bw
모든 확장 정규 문법은 새로운 비말단 기호를 도입하여 엄격한(strict) 정규 문법 형태로 변환할 수 있으며, 동일한 언어를 생성한다.
주요 성질
유한 오토마타와의 대응 관계: 모든 정규 문법에 대응하는 유한 오토마타가 적어도 하나 존재하며, 반대로 모든 유한 오토마타에 대응하는 정규 문법이 적어도 하나 존재한다. 특히, 엄격한 우선형 문법의 규칙과 비결정적 유한 오토마타(NFA)의 전이 함수 사이에는 일대일 대응 관계가 성립한다.
좌선형과 우선형의 관계: 좌선형 문법으로 생성되는 언어는 동등한 우선형 문법으로 변환할 수 있으며, 그 역도 성립한다. 따라서 두 형식 모두 정규 언어를 표현하는 데 있어 동등한 표현력을 가진다.
정규 표현과의 대응: 정규 문법은 정규 표현(regular expression)과도 대응한다. 정규 문법으로 기술된 언어는 항상 정규 표현으로 나타낼 수 있으며, 그 역도 성립한다.
예시
다음은 우선형 문법의 예시이다.
- N = {S, A}
- Σ = {a, b, c}
- P:
- S → aS
- S → bA
- A → ε
- A → cA
이 문법은 정규 표현 a*bc*에 해당하는 언어, 즉 임의의 개수의 'a' 뒤에 하나의 'b'가 오고 다시 임의의 개수의 'c'가 오는 모든 문자열의 집합을 생성한다.
프로그래밍 언어에서의 활용
정규 문법은 컴파일러의 어휘 분석(lexical analysis) 단계에서 소스 코드를 토큰(token) 단위로 분해하는 데 사용된다. 식별자, 숫자, 연산자 등의 토큰 패턴은 정규 문법으로 기술되며, 이를 유한 오토마타로 구현하여 효율적인 어휘 분석기를 구성할 수 있다.
참고 사항
일부 교재에서는 빈 문자열 생성 규칙(A → ε)을 허용하지 않기도 한다. 이 경우 빈 문자열을 포함하지 않는 정규 언어만 생성할 수 있다. 또한 정규 언어는 정규 문법뿐만 아니라 비정규 문법(non-regular grammar)으로도 기술될 수 있으나, 정규 문법은 오직 정규 언어만을 생성한다.
