[Compiler] 2.1. Regular Languages

형식 언어(formal language)

범위 정의

Regular language ⊂ Context-free language ⊂ Context-sensitive language ⊂ Recursively enumerable language

언어 정의

• Alphabet(Σ) : 기호들의 유한 집합
  $Letter = {\Sigma}^L = \{A,B,C,{\dots},Z,a,b,c,{\dots}z\}$
  $Digit = {\Sigma}^D = \{0,1,2,{\dots},9\}$
• String(s) : alphabet으로 구성된 유한 집합
  $if \text{ } {\Sigma} = \{0\}, s=0,00,000\dots$
  $if \text{ } {\Sigma} = \{a,b\}, s=a,b,aa,bb,ab,ba,aaa,aab\dots$
  • Notation
    $|s|$ : s의 길이
    $s_1 s_2$ : 두 문자열 s1과 s2의 (순서 있는) 연속 합성. $s_1 s_2$와 $s_2 s_1$은 다르다.
    $\epsilon$: 빈 문자열
    $s^i$: s의 지수연산, 즉 i번의 합성
• language(L) : 어떤 alphabet으로 이루어진 string들의 유무한 집합
  $if \text{ } {\Sigma} = \{a,b\}, L_1 = \{a,ab,ba,aba\} \text{ and } L_2 = \{a,aa,b,ab,ba,aaa,\dots\}$
  • Notation
    $L_1 \cup L_2$ : L1과 L2의 합집합
    $L_1 L_2$ : L1과 L2의 합성
    e.g. $L_1 L_2 = \{ab,aaa,abb,abaa\}\text{ s.t. }L_1 = \{a,ab\},L_2=\{b,aa\}$
    $L^i$: L을 i번 합성
    $L^*$ : L을 0번 이상 합성
    $L^+$ : L을 1번 이상 합성

Regular Expression

기본 정규 표현의 연산으로 표현할 수 있으면 정규 표현이다

• basic regular expreesion
  $\epsilon$ : $L(\epsilon)=\{\epsilon\}$
  $a$ : $L(a) = \{a\}\text{, where }a\text{ is a symbol in alphabet }\Sigma$
  $r_1|r_2$ : $L(r_1|r_2) = L(r_1)\cup L(r_2)$
  (교환법칙, 결합법칙 성립)
  $r_1r_2$ : $L(r_1r_2) = L(r_1)L(r_2) = \{s_1s_2 | s_1\in L(r_1), s_2\in L(r_2)\}$
  (교환법칙 미성립, 결합법칙 성립, 분배법칙 성립)
  $r^*$ : $L(r^*) = \bigcup_{i\geq 0}L(r^i)$
  (이때, $a^{**} = a^*$)

• 연산 우선순위
  *,+ > 합성(concatenation) > union(|)