Regular expression

Regular expressions(정규표현)

정규표현(Regular expression)

• 정규언어를 표현하는 대수적인 방법
• e가 정규표현이면 L(e)는 e를 정의하는 언어

정규표현의 정의

1. a가 어떤 기호이면, a는 정규표현이고, L(a) = {a}
2. $\epsilon$은 정규 표현이고, L($\epsilon$) = {$\epsilon$}
3. $\varnothing$은 정규 표현이고, L($\varnothing$) = $\varnothing$

유도식

1. r과 s가 정규 표현이면, r+s도 정규 표현이고, $L(r+s) = L(r) + L(s)$
   • + 대신에 | 를 쓰기도 한다.
   • L(r|s) = L(r) $\cup$ L(s)
   • {r, s}
2. r과 s가 정규 표현이면, rs도 정규 표현이고, $L(rs) = L(r)L(s)$
   • 연결
   • {rs}
3. r이 정규 표현이면, $r^*$도 정규 표현이고, $L(r^*) = (L(r))^*$
   • {r}$^*$ = {$\epsilon$, r, rr, ...}

연산자 우선순위

• 괄호는 연산자 그룹핑에 쓰임
• () → * → 연결 → +

※주의

• 정규 표현은 카운팅이 불가능
  • $\{ a^nba^n | n\ge 0\} \not= a^*ba^*$
• pumping lemma를 통해 정규 표현이 아님을 증명

정규 표현에 대한 대수 법칙

• $(\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)$ (+ 에 대한 결합 법칙)
• $(\alpha\beta)\gamma = \alpha(\beta\gamma)$ (접속에 대한 결합 법칙)
• $\alpha + \beta = \beta + \alpha$ (+ 에 대한 교환 법칙)
• $\alpha + \alpha = \alpha$
• $\alpha(\beta + \gamma) = \alpha\beta + \alpha\gamma$ (분배법칙)
• $(\beta + \gamma)\alpha = \beta\alpha + \gamma\alpha$ (분배 법칙)
• $\varepsilon\alpha = \alpha = \alpha\varepsilon$ (접속 연산의 항등원)
• $\alpha^* = \varepsilon + \alpha\alpha^*$
• $(\alpha^*)^* = \alpha^*$