• 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

  1. \(∅, λ,\) and \(a ∈ Σ\) are all regular expressions. These are called primitive regular expressions.
  2. If \(r_1\) and \(r_2\) are regular expressions, so are \(r_1 + r_2, \ r_1 · r_2, \ {r_1}^* \\), and (\(r_1\)).
  3. 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).

주어진 알파벳 \(Σ\)에 대하여,

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

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

  1. \(∅\) is a regular expression denoting the empty set,
  2. \(λ\) is a regular expression denoting \(\{λ\}\),
  3. For every \(a ∈ Σ\), a is a regular expression denoting \(\{a\}\).
    If \(r_1\) and \(r_2\) are regular expressions, then
  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))*\).

정규 표현 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{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, 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^{2n} b^{2m+1} : n ≥ 0, m ≥ 0 \}.\]

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

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