정규식과 정규 문법

정규식 (Regular Expressions)

언어는 집합으로 표현되고, 집합 연산자를 통해 새로운 언어를 표현합니다.

이때, 집합 대신 간결한 정규식으로 대신하여 사용합니다.

 

집합 연산자 ∪, *, ·, 는 각각 정규식 연산자인 +, *, ·(생략 가능) 으로 치환됩니다.

 

정규식은 정규 언어의 표현을 단순화 한것이므로, 실제로는 정규 언어를 의미합니다.

ex) {a} = a, {a} ∪ {b} ∪ {c} = a+b+c ... etc

 

기호 ∑에 대해서,

1. Ø, λ, a ∈ ∑ 는 정규 표현입니다.

2. 두 정규 표현 r1, r2가 주어졌을 때, r1+r2, r1r2, r1*는 정규 표현입니다.

3. 1, 2로 얻어지는 식은 정규 표현입니다.

4. 1, 2, 3에 의해 유도되지 않는 표현은 정규 표현이 아닙니다.

 

한 정규식은 여러 개의 스트링을 표현할 수 있고, 이를 집합으로 표기하면, 언어에 해당됩니다.

정규언어는 정규식에 의해서 표현될 수 있는 언어입니다. (이에 더해 유한 오토마타(DFA, NFA)에 의해 인식되는 언어이기도 함)

 

정규식 연산자의 우선순위는 *, ·, + 순으로 정의됩니다.

 

정규 언어는 정규식에 의해서 표현되고, 유한 오토마타에 의해 인식되는 언어입니다.

따라서, 정규식 r이 주어진 경우, L(r) 언어를 받아들이는 NFA가 존재합니다. 그러므로 L(r)은 정규 언어 입니다.

 

정규식에는 덧셈의 교환법칙, λ와 Ø의 곱셈에서 교환법칙, 곱셈의 분배법칙, 곱셈의 결합법칙이 적용됩니다.

이에 추가로 다음 법칙들이 적용됩니다.

 

rr* = r+

r* = λ + rr*

r(sr)* = (rs)*r

(r*s)* = λ + (r + s)*s

(rs*)* = λ + r(r + s)*

s(r + λ)*(r + λ) + s = sr*

(r + s)* = (r* + s*)* = (r*s*)* = (r*s)*r* = r*(sr*)*

 

정규식은 NFA로 표현할 수 있었는데, 반대로 NFA 또한 정규식으로 변환 가능합니다.

 

NFA M = (Q, ∑, δ, q0, F) 가 주어졌을 때,

상태 qi 에 해당하는 언어 Ai는 Ai = {w ∈ ∑* | δ(qi, w) ∩ F ≠ Ø} 로 정의됩니다. (qi 상태로부터 최종 상태로 이동할 때 연관된 스트링들의 집합)

 

그 결과 L(M) = A0로, NFA M이 받아들이는 언어가 정의됩니다.

 

정규 문법 (Regular Grammars)

문법은 표기할 때, 우선형 문법(Right - Linear Grammar)와 좌선형 문법(Left - Linear Grammar)로 나뉘는데, 각각 넌터미널의 위치에 따른 차이가 있습니다.

 

ex) 우선형 문법 : A → xB, 좌선형 문법 : A → Bx

 

동일한 언어에 대해서 정규 문법은 정규식으로 변환이 가능하고, 정규식은 오토마타로 변환이 가능합니다.

 

정리 )

Regular Grammar ↔ Regular Expressions, NFA OR DFA

Regular Expressions ↔ Regular Grammar, NFA OR DFA

NFA OR DFA ↔ Regular Expressions, Regular Grammar