정의
정규 문법(regular grammar)은 형식 언어 이론에서 사용되는 문법의 한 종류로, 생성 규칙이 특정한 형태만을 허용한다. 정규 문법은 두 가지 형태로 구분되며, 각각 오른쪽 선형 문법(right-linear grammar)과 왼쪽 선형 문법(left-linear grammar)이라고 한다. 오른쪽 선형 문법의 모든 생산 규칙은 $A \rightarrow aB$ 또는 $A \rightarrow a$ (또는 $A \rightarrow \epsilon$)의 형태이며, 여기서 $A, B$는 비단말 기호, $a$는 단말 기호, $\epsilon$은 빈 문자열을 나타낸다. 왼쪽 선형 문법은 $A \rightarrow Ba$ 형태의 규칙을 허용한다.
관계
정규 문법이 생성하는 언어 집합은 정규 언어(regular language)와 정확히 일치한다. 정규 언어는 유한 자동장치(Deterministic Finite Automaton, DFA; Nondeterministic Finite Automaton, NFA)와 정규 표현식(regular expression)으로도 표현할 수 있다. 따라서 정규 문법, 정규 표현식, 유한 자동장치는 서로 동등한 표현 능력을 가진다.
계층적 위치
정규 문법은 촘스키 계층(Chomsky hierarchy)에서 가장 하위에 해당한다.
- 제0형(무제한 문법) → 재귀열거 언어
- 제1형(문맥 자유 문법) → 문맥 자유 언어
- 제2형(문맥 의존 문법) → 문맥 의존 언어
- 제3형(정규 문법) → 정규 언어
특징
- 생성 규칙의 제한성: 비단말 기호가 단말 기호의 바로 앞(또는 뒤) 하나만 위치한다.
- 결정 가능성: 정규 언어에 대한 멤버십 테스트(특정 문자열이 해당 언어에 속하는지 여부)는 선형 시간(O(n)) 알고리즘으로 수행 가능하다.
- 폐쇄성: 정규 언어는 합집합, 교집합, 여집합, 연결(concatenation), 케레(Kleene star) 연산에 대해 닫혀 있다.
예시
- 언어 $L = {a^n b \mid n \ge 0}$는 오른쪽 선형 규칙
$$ S \rightarrow aS \mid b $$
로 기술할 수 있다. - 언어 $L = {(ab)^n \mid n \ge 0}$는 오른쪽 선형 규칙
$$ S \rightarrow aA,; A \rightarrow bS \mid \epsilon $$
로 표현된다.
응용
정규 문법은 컴파일러의 렉서(lexer) 설계, 문자열 검색, 프로토콜 분석 등에서 사용된다. 실제 구현에서는 정규 표현식을 기반으로 하는 라이브러리(예: POSIX regex, PCRE)가 정규 문법과 동등한 기능을 제공한다.
한계
정규 문법은 중첩 구조나 균형 잡힌 괄호와 같은 문맥 자유 언어의 특성을 표현할 수 없으며, 이러한 경우에는 문맥 자유 문법(context-free grammar)이 필요하다.
참고
- Hopcroft, J. E., & Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation.
- Sipser, M. (2012). Introduction to the Theory of Computation.
(이 문서는 위키백과 스타일을 참고하여 객관적·중립적으로 작성되었습니다.)