Theory of computation (5)

본 내용은 KOCW 한양대학교 “오토마타 및 계산이론” 강좌 6강을 보며 정리한 내용입니다.

Regular Expression

language를 표현할수 있는 방법은 3가지가 있습니다.

첫번째는 grammer를 이용하여 grammer로 derivation 하는 모든 sentence 들을 language로 하는것입니다.

두번째는 DFA나 NFA가 accept 하는 string 들을 language 라고 하는 것입니다.

마지막 방법인 regular expression 입니다.

• $\phi$, $\lambda$, $a \in \Sigma$

  • $\phi, \lambda$는 서로 다른 것입니다.

    • $\phi$ = $\{\}$ 는 empty set 입니다.
    • $\lambda$ = $\{\lambda\}$ null string이 있다는 것입니다.

• $r_1+r_2$, $r_1 r_2$, $r_1^* $, $(r_1)$

  • $L(r_1)+L(r_2) = L(r_1) \cup L(r_2)$

    • $a+b = \{a\} \cup \{b\}= \{a,b\}$

  • $L(r_1)L(r_2)$ concatenation

    • $\{a+b\}\{c+d\} = \{ac, ad, bc, bd\}$

  • $L(r_1)^* $

    • concatenation 을 0번부터 하는것입니다.
    • $a^* = \{\lambda, a, aa, \cdots \}$

  • $L((r_1)) = L(r_1)$

    • language 표현 자체는 변하는게 없지만 우선순위를 정할때 사용합니다.

예제 1)

$$(a+b)^* (a+bb)$$

$(a+b)^* = \{\lambda, a, b, aa, bb, ab, ba \cdots\}$
a,b로 표현할수 있는 모든 language를 나타냅니다.

$(a+bb)$를 $(a+b)^* $ 뒤에 concatenation 한다는 것 $a,b$ 로 나타낼수 있는 language 뒤에 $a$ 를 붙이거나 $bb$ 를 붙이는 language 를 표현합니다.

예제 2)

$$(aa)^* (bb)^* b$$

$a$ 짝수개와 $b$ 홀수개를 concatenation 한 language 입니다

예제 3)

조건을 만족하는 language 를 나타내는 regular expression 다음과 같습니다.

$$1001 \in L$$ $$101 \notin L$$

가운데 0이 두개가 들어가야 하므로

$$(0+1)^* 00 (0+1)^*$$