형식언어와 오토마타.03.01

정규 표현(Regular Expression)

CHAPTER 3. REGULAR LANGUAGES AND REGULAR GRAMMARS
- 3.1 REGULAR EXPRESSIONS
챕터 3. 정규 언어와 정규 문법
- 3.1 정규 표현

According to our definition, a language is regular if there exists a finite accepter for it.

finite accepter가 있는 언어는 정규 언어이다.

정규 표현(Regular Expression)

DEFINITION 3.1
Let $Σ$ be a given alphabet. Then

$∅, λ,$ and $a ∈ Σ$ are all regular expressions. These are called primitive regular expressions.

If $r_1$ and $r_2$ are regular expressions, so are $r_1 + r_2, \ r_1 · r_2, \ {r_1}^* \\), and (\(r_1$ ).

A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).

주어진 알파벳 $Σ$ 에 대하여,

$∅, λ,$ 그리고 $a ∈ Σ$ 는 모두 정규 표현이며, 기본 정규 표현(primitive regular expressions)이라 부른다.
$r_{1}, r_{2}$ 가 정규 표현이면,
- $r_1 + r_2$ 도 정규 표현이다.
- $r_{1} \cdot r_{2}$ 도 정규 표현이다.
  - 참고: $\cdot$ $⋅$ 는 concatenation 이다.
- ${r_1}^*$ 도 정규 표현이다.
- $(r_1)$ 도 정규 표현이다.
기본 정규 표현에 2번 규칙을 유한한 횟수만큼 적용해서 나오는 문자열은 모두 정규 표현이다.

DEFINITION 3.2
The language $L(r)$ denoted by any regular expression $r$ is defined by the following rules.

$∅$ is a regular expression denoting the empty set,

$λ$ is a regular expression denoting $\{λ\}$ ,

For every $a ∈ Σ$ , a is a regular expression denoting $\{a\}$ .
If $r_1$ and $r_2$ are regular expressions, then

$L (r_1 + r_2) = L (r_1) ∪ L (r_2)$ ,

$L (r_1 · r_2) = L (r_1) L (r_2)$ ,

$L ((r_1)) = L (r_1)$ ,

$L ({r_1}^* = (L (r_1))*$ .

정규 표현 r로 표현되는 언어 $L(r)$ 은 다음의 규칙들로 정의할 수 있다.

재귀를 종료하기 위한 규칙
- 1 . $∅$ 은 공집합을 의미하는 정규 표현이다.
- 2 . $λ$ 는 $\{λ\}$ 를 의미하는 정규 표현이다.
- 3 . $Σ$ 의 원소인 $a$ 에 대해, $a$ 는 $\{a\}$ 를 의미하는 정규 표현이다.
재귀적으로 $L (r)$ 을 간단하게 변환하는 규칙.
- 4 . $L (r_1 + r_2) = L (r_1) ∪ L (r_2)$ ,
- 5 . $L (r_1 · r_2) = L (r_1) L (r_2)$ ,
- 6 . $L ((r_1)) = L (r_1)$ ,
- 7 . $L ({r_1}^* = (L (r_1))*$ .

두 정규 표현이 같은 언어를 표현하는 경우 동치 관계에 있다고 한다.

예제 3.2

Exhibit the language $L (a^* · (a + b))$ in set notation.

언어 $L (a^* · (a + b))$ 를 집합 형식으로 나열하라.

\begin{matrix} L (a^{*} \cdot (a + b)) = L (a^{*}) L (a + b) = (L (a))^{*} (L (a) \cup L (b)) = (L (a))^{*} {a, b} = {λ, a, a a, a a a, . . .} {a, b} = {λ} {a, b} \cup {a} {a, b} \cup {a a} {a, b} \cup . . . = {a, b, a a, a b, a a a, a a b, a a a a, a a a b, a a a a a, a a a a b, . . .} \end{matrix}

$\begin{array}{l} L (a^* · (a + b)) \\ \ = L(a^*) L(a+b) \\ \ = (L(a))^* ( L(a) \cup L(b) ) \\ \ = (L(a))^* \color{red}{\{ a, b \}} \\ \ = \color{blue}{\{ λ, a, aa, aaa, ... \}} \color{red}{\{ a, b \}} \\ \ = \{ λ \} \{ a, b \} \cup \{ a \} \{ a, b \} \cup \{ aa \} \{ a, b \} \cup ... \\ \ = \{ a, b, aa, ab, aaa, aab, aaaa, aaab, \\ \quad aaaaa, aaaab, ... \} \end{array}$

참고

우리에게 익숙한 perl, JavaScript 정규표현식과 비교해 본다면?
- *은 똑같은 의미를 갖는다.
- $r_1 \cdot r_2$ 는 concat이므로 $r_1 r_2$ 와 같다. 즉, 무시해도 된다.
- $(a+b) = \{ a \} \cup \{ b \}$ 이므로 [ab]와 같다.
- 따라서 이 문제는 ^a*[ab]$ 와 같다.

예제 3.3

$Σ = {a, b}$ 에 대한 정규 표현 $r = (a + b)^* (a + bb)$ 은 다음 언어를 표현한다.

L (r) = {a, b b, a a, a b b, b a, b b b, . . .}

$L(r) = \{ a, bb, aa, abb, ba, bbb, ... \}$

이번에도 우리에게 익숙한 perl, JavaScript 정규표현식으로 표현해 보자.

$(a+b)^*$ 는 [ab]* 이다.
$(a + bb)$ 는 (a|bb) 이다.
그러므로 ^[ab]*(a|bb)$ 이다.
- 캡처 그룹을 안 쓴다면 ^[ab]*(?:a|bb)$.

예제 3.4

$r = (aa)^* (bb)^* b$ 은 짝수개 a 다음에 홀수개의 b가 오는 모든 문자열들로 이루어지는 언어를 표현한다.

L (r) = {a^{2 n} b^{2 m + 1} : n \geq 0, m \geq 0} .

$L(r) = \{ a^{2n} b^{2m+1} : n ≥ 0, m ≥ 0 \}.$

이번에도 우리에게 익숙한 perl, JavaScript 정규표현식으로 표현해 보면…

^(aa)*(bb)*b$
- 재미있게도 원래 정규 표현 $r$ 과 똑같은 형태의 정규표현식이 나온다.