정규 문법
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
정규 문법은 생성 규칙의 형태에 따라 우측 정규 문법과 좌측 정규 문법으로 나뉘며, 주어진 문법에 의해 설명되는 언어는 단말 기호만 포함하고 시작 기호로부터 생성 규칙을 반복적으로 적용하여 파생될 수 있는 모든 문자열의 집합이다. 정규 문법은 정규 언어만을 표현할 수 있으며, 유한 오토마타나 정규 표현식과 등가이다. 또한, 모든 정규 문법은 문맥 자유 문법에 포함된다.
더 읽어볼만한 페이지
- 형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다. - 형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다. - 언어학에 관한 - 세례명
세례명은 기독교에서 세례를 받을 때 받는 새로운 이름으로, 예수 그리스도 안에서 새롭게 태어남을 의미하며, 성경 속 인물들의 이름 변화에서 유래하여 중세 이후 유럽에서 일반적인 이름 형태로 정착되었고, 수호성인의 이름에서 따와 이름 축일로 기념되기도 한다. - 언어학에 관한 - 개명
개명은 개인이나 법인이 이름을 바꾸는 행위로, 결혼, 이혼, 이민, 종교 개종, 성 정체성 확인, 사회적 이미지 개선, 범죄 회피 등 여러 이유로 행해지며, 절차는 국가별로 다르지만 법적 제약과 고려 사항이 따른다.
| 정규 문법 | |
|---|---|
| 기본 정보 | |
| 이름 | 정규 문법 |
| 로마자 표기 | Jeonggyu Munbeop |
| 영문명 | Regular grammar |
| 정의 | |
| 유형 | 형식 문법의 한 종류 |
| 설명 | 형식 언어 이론에서 정규 언어를 생성하는 형식 문법. 정규 문법은 촘스키 위계의 3형 문법이다. |
| 특징 | |
| 규칙 형태 | 모든 생성 규칙이 특정한 형태를 갖는다. (아래 '형태' 섹션 참조) |
| 표현 능력 | 유한 상태 기계로 인식 가능한 언어를 생성 |
| 응용 | 컴파일러의 어휘 분석 패턴 매칭 자연어 처리의 일부 영역 |
| 형태 | |
| 우측 선형 문법 (Right-Regular Grammar) | 모든 생성 규칙이 A → aB 또는 A → a 형태. 여기서 A, B는 비단말 기호, a는 단말 기호열 (terminal string) |
| 좌측 선형 문법 (Left-Regular Grammar) | 모든 생성 규칙이 A → Ba 또는 A → a 형태. 여기서 A, B는 비단말 기호, a는 단말 기호열 |
| 주의 사항 | 좌측 선형 문법과 우측 선형 문법을 혼합하여 사용할 수 없음. 혼합 시 정규 언어 이상의 언어를 생성할 수 있음 |
| 예시 | |
| 우측 선형 문법 예시 | S → aS S → b |
| 설명 | 위의 문법은 'a'가 0개 이상 반복되고 그 뒤에 'b'가 오는 형태의 문자열을 생성하는 정규 문법이다. (a*b) |
| 관련 개념 | |
| 관련 개념 | 정규 표현식 유한 상태 기계 촘스키 위계 문맥 자유 문법 |
2. 정규 문법의 종류
정규 문법은 생성 규칙의 형태에 따라 크게 두 가지, 즉 우측 정규 문법과 좌측 정규 문법으로 나눌 수 있다. 이 둘은 비단말 기호가 생성 규칙의 오른쪽에 나타나는 위치에 따라 구분된다.
- 우측 정규 문법(우측 선형 문법): 생성 규칙이 `A → a` 또는 `A → aB` 형태를 가진다. (비단말 기호 B가 가장 오른쪽에 위치)
- 좌측 정규 문법(좌측 선형 문법): 생성 규칙이 `A → a` 또는 `A → Ba` 형태를 가진다. (비단말 기호 B가 가장 왼쪽에 위치)
이 두 종류의 규칙은 하나의 문법 내에서 섞어 쓸 수 없다. 예를 들어, 우측 규칙(`S → aT`)과 좌측 규칙(`T → Sb`)을 함께 사용하면 더 이상 정규 문법이 아니며, 생성되는 언어도 정규 언어가 아닐 수 있다.
또한, 생성 규칙의 우변에 여러 개의 단말 기호 문자열을 허용하는 확장된 정규 문법도 있다. 이는 확장된 우측 정규 문법과 확장된 좌측 정규 문법으로 나뉜다.
중요한 점은 우측 정규 문법, 좌측 정규 문법, 확장된 정규 문법 모두 유한 오토마타나 정규 표현식과 동일한 능력, 즉 모든 정규 언어를 정의할 수 있다는 것이다. 즉, 이들은 표현력 면에서 동등하며, 두 문법이 동일한 언어를 설명하는 경우 약하게 동치라고 한다.
모든 정규 문법은 문맥 자유 문법의 한 종류이다. 하지만 정규 문법은 좌측 규칙 또는 우측 규칙 중 하나만 사용해야 하므로, 두 규칙을 자유롭게 혼합하여 사용하는 문맥 자유 문법보다는 표현할 수 있는 언어의 범위가 좁다.
일부 정의에서는 빈 문자열 ε를 생성하는 규칙(`A → ε`)을 허용하지 않기도 한다.
2. 1. 우측 정규 문법 (Right Regular Grammar)
''우측 정규 문법'' (또는 우측 선형 문법)은 형식 문법(''N'', Σ, ''P'', ''S'')의 한 종류로, ''P''에 포함된 모든 생성 규칙이 다음 세 가지 형식 중 하나를 따른다.# ''A'' → ''a''
# ''A'' → ''aB''
# ''A'' → ε
여기서 ''A'', ''B'', ''S''는 비단말 기호 (''N''에 속함), ''a''는 단말 기호 (Σ에 속함), ε는 빈 문자열 (길이가 0인 문자열)을 나타낸다. ''S''는 시작 기호이다.
참고로, 좌측 정규 문법에서는 규칙 형식이 ''A'' → ''Ba'' 형태를 가진다. 정규 문법에서는 우측 규칙과 좌측 규칙을 혼합하여 사용할 수 없다. 예를 들어, { ''S''→''aT'', ''T''→''Sb'', S→ε }와 같이 규칙을 섞으면 정규 문법이 아니며, 생성되는 언어(a가 n번 나타나고 그 뒤에 b가 n번 나타나는 모든 문자열의 집합, 예: ab, aabb, aaabbb 등) 역시 정규 언어가 아니다.
일부 교과서나 논문에서는 빈 문자열을 생성하는 규칙(''A'' → ε)을 허용하지 않기도 한다. 이 경우 해당 문법으로 생성되는 언어에는 빈 문자열이 포함되지 않는다고 가정한다.
다음은 우측 정규 문법 ''G''의 예시이다.
- ''N'' = {''S'', ''A''} (비단말 기호 집합)
- Σ = {''a'', ''b'', ''c''} (단말 기호 집합)
- ''P'' (생성 규칙 집합):
:: ''S'' → ''aS''
:: ''S'' → ''bA''
:: ''A'' → ε
:: ''A'' → ''cA''
- ''S'' (시작 기호)
이 문법 ''G''는 정규 표현식 `a*bc*`와 동등한 언어를 생성한다.
2. 2. 좌측 정규 문법 (Left Regular Grammar)
'''좌측 정규 문법''' (또는 좌측 선형 문법)은 모든 생성 규칙이 다음 형식 중 하나를 따르는 형식 문법이다.| 형식 | 설명 |
|---|---|
| A → a | 비단말 기호 A는 단말 기호 a로 대체될 수 있다. |
| A → Ba | 비단말 기호 A는 비단말 기호 B와 단말 기호 a의 순서로 대체될 수 있다. |
| A → ε | 비단말 기호 A는 빈 문자열 ε로 대체될 수 있다. |
여기서 ''A'', ''B''는 비단말 기호이고, ''a''는 단말 기호이며, ε는 빈 문자열, 즉 길이가 0인 문자열을 나타낸다.
2. 3. 확장된 정규 문법 (Extended Regular Grammar)
확장된 정규 문법은 생성 규칙의 우변에 (비어 있을 수도 있는) 단말 기호 문자열을 허용하도록 정의를 확장한 문법이다. 이는 확장된 우측 정규 문법과 확장된 좌측 정규 문법으로 나뉜다.2. 3. 1. 확장된 우측 정규 문법
''확장된 우측 정규 문법''은 모든 규칙이 다음 중 하나를 따르는 문법이다.# ''A'' → ''w'', 여기서 ''A''는 비단말 기호 ''N''에 속하며, ''w''는 (비어 있을 수도 있는) 단말 기호 문자열 Σ*에 속한다.
# ''A'' → ''wB'', 여기서 ''A''와 ''B''는 ''N''에 속하며, ''w''는 Σ*에 속한다.
일부 저자는 이러한 유형의 문법을 ''우측 정규 문법'' (또는 ''우측 선형 문법'')[1]이라고 부르며, 엄격한 우측 정규 문법 (또는 ''엄격한 우측 선형 문법'')이라고 부른다.[2]
2. 3. 2. 확장된 좌측 정규 문법
''확장된 좌측 정규 문법''은 모든 규칙이 다음 중 하나를 따르는 문법이다.# ''A'' → ''w'', 여기서 ''A''는 비단말 기호 ''N''에 속하며, ''w''는 (비어 있을 수도 있는) 단말 기호 문자열 Σ*에 속한다.
# ''A'' → ''Bw'', 여기서 ''A''와 ''B''는 ''N''에 속하며, ''w''는 Σ*에 속한다.
3. 표현 능력 (Expressive Power)
(엄격한) 우측 정규 문법의 규칙과 비결정적 유한 오토마타의 규칙 사이에는 직접적인 일대일 대응 관계가 성립한다. 이 때문에 우측 정규 문법은 해당 오토마타가 인식하는 언어와 정확히 동일한 언어를 생성한다.[3] 결과적으로, 우측 정규 문법은 모든 정규 언어를 정확하게 생성할 수 있다. 좌측 정규 문법은 이러한 모든 정규 언어의 역(reverseeng)을 생성하며, 이는 결과적으로 모든 정규 언어를 표현할 수 있음을 의미한다. 즉, 우측 정규 문법과 좌측 정규 문법은 표현 능력 면에서 동등하며, 모두 정규 언어 전체를 생성할 수 있다.
모든 엄격한 우측 정규 문법은 확장 우측 정규 문법에 해당한다. 반대로, 모든 확장 우측 정규 문법은 새로운 비단말 기호를 추가하는 방식으로 엄격한 우측 정규 문법으로 변환될 수 있으며, 이 변환 과정에서 생성되는 언어는 동일하게 유지된다. 따라서 확장 우측 정규 문법 역시 모든 정규 언어를 생성할 수 있다. 확장 좌측 정규 문법의 경우도 마찬가지이다.
만약 빈 문자열(ε)을 생성하는 규칙이 허용되지 않는다면, 해당 정규 문법은 빈 문자열을 포함하지 않는 정규 언어만을 생성할 수 있다.[4]
정규 문법은 오직 정규 언어만을 생성할 수 있다. 하지만 그 역은 성립하지 않는데, 이는 정규 언어가 정규 문법이 아닌 다른 종류의 문법으로도 생성될 수 있기 때문이다.
만약 하나의 문법 내에서 좌측 정규 규칙과 우측 정규 규칙을 혼합하여 사용하는 것이 허용된다면, 그 문법은 여전히 선형 문법의 정의에는 부합하지만, 반드시 정규 문법인 것은 아니다. 더 중요한 점은, 이렇게 혼합된 규칙을 사용하는 문법은 정규 언어가 아닌 언어를 생성할 수도 있다는 것이다. 실제로 모든 선형 문법은 이러한 혼합된 형태로 쉽게 변환될 수 있으며, 따라서 이러한 형태의 문법은 비정규 언어를 포함한 모든 선형 언어를 생성할 수 있다.
예를 들어, 비단말 기호 집합 ''N'' = {S, A}, 단말 기호 집합 Σ = {a, b}, 시작 기호 ''S'', 그리고 다음과 같은 생성 규칙 ''P''를 가진 문법 ''G''를 생각해보자.
: S → aA
: A → Sb
: S → ε
이 문법 ''G''는 좌측 정규 규칙(A → Sb)과 우측 정규 규칙(S → aA)을 혼합하여 사용하고 있으며, 대표적인 비정규 선형 언어인 를 생성한다.
정규 문법은 모든 정규 언어를 표현할 수 있으며, 이러한 능력은 유한 오토마타나 정규 표현식과 동등하다.
모든 정규 문법은 문맥 자유 문법의 정의에 포함된다. 문맥 자유 문법은 좌측 정규 규칙과 우측 정규 규칙의 조합을 허용하여 더 넓은 범위의 언어인 문맥 자유 언어를 표현할 수 있다. 반면, 정규 문법은 좌측 정규 규칙 또는 우측 정규 규칙 중 한 종류만을 사용하기 때문에, 더 제한적인 언어 집합인 정규 언어만을 표현할 수 있다.
4. 예시
다음은 비단말 기호 집합 ''N'' = {S, A}, 단말 기호 집합 Σ = {a, b, c}이고, 다음 생성 규칙 P로 구성된 우측 정규 문법 ''G''의 예시이다. 여기서 S는 시작 기호이다.
- S → aS
- S → bA
- A → ε
- A → cA
이 문법은 정규 표현식 '''a\*bc\*'''와 동일한 언어를 설명한다. 즉, 임의의 개수의 'a' 뒤에 하나의 'b'가 오고, 그 뒤에 임의의 개수의 'c'가 오는 모든 문자열의 집합을 나타낸다.
프로그래밍 언어 분야의 예로, 부동 소수점 숫자를 나타내는 모든 문자열의 집합은 다음과 같은 확장된 우측 정규 문법 ''G''로 설명할 수 있다. ''N'' = {S, A, B, C, D, E, F}, Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −, ., e}이며, S는 시작 기호이다. 생성 규칙 P는 다음과 같다.
| S 규칙 | A 규칙 | B 규칙 | C 규칙 | D 규칙 | E 규칙 | F 규칙 |
|---|---|---|---|---|---|---|
| S → +A | A → 0A | B → 0C | C → 0C | D → +E | E → 0F | F → 0F |
| S → −A | A → 1A | B → 1C | C → 1C | D → −E | E → 1F | F → 1F |
| S → A | A → 2A | B → 2C | C → 2C | D → E | E → 2F | F → 2F |
| A → 3A | B → 3C | C → 3C | E → 3F | F → 3F | ||
| A → 4A | B → 4C | C → 4C | E → 4F | F → 4F | ||
| A → 5A | B → 5C | C → 5C | E → 5F | F → 5F | ||
| A → 6A | B → 6C | C → 6C | E → 6F | F → 6F | ||
| A → 7A | B → 7C | C → 7C | E → 7F | F → 7F | ||
| A → 8A | B → 8C | C → 8C | E → 8F | F → 8F | ||
| A → 9A | B → 9C | C → 9C | E → 9F | F → 9F | ||
| A → .B | C → eD | F → ε | ||||
| A → B | C → ε |
5. 정규 문법과 문맥 자유 문법
정규 문법은 모두 문맥 자유 문법에 포함된다. 즉, 모든 정규 문법은 문맥 자유 문법의 한 종류라고 할 수 있지만, 모든 문맥 자유 문법이 정규 문법인 것은 아니다.
문맥 자유 문법과 정규 문법의 주요 차이점은 생성 규칙을 만드는 방식에 있다. 모든 문맥 자유 문법은 좌정규 규칙과 우정규 규칙을 함께 사용하여 정의할 수 있으며, 이를 통해 모든 문맥 자유 언어를 표현하는 것이 가능하다. 하지만 정규 문법은 좌정규 규칙 또는 우정규 규칙 중 하나의 종류만을 사용해야 하며, 두 종류의 규칙을 동시에 섞어 쓸 수 없다. 이러한 제약 때문에 정규 문법은 문맥 자유 언어보다 더 한정된 범위의 언어, 즉 정규 언어만을 기술할 수 있다.
참고로, 정규 문법은 모든 정규 언어를 기술할 수 있다는 점에서 유한 오토마타나 정규 표현식과 동일한 표현 능력을 가진다. 또한, 우정규 문법으로 정의할 수 있는 언어는 좌정규 문법으로도 동일하게 정의할 수 있다. 정의에 따라서는 정규 문법에서 빈 문자열(ε, 엡실론)을 생성하는 규칙을 허용하지 않는 경우도 있다.
참조
[1]
서적
Introduction to Automata Theory, Languages, and Computation
https://archive.org/[...]
Addison-Wesley
[2]
서적
[3]
서적
[4]
서적
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com