[계산이론](7)[regular expression]

regular expression

regular operation을 이용해서 regular language를 표현할 수 있다!

• 피연산자는 집합의 형태이다.
  간혹가다 그냥 알파벳에 0∪1처럼 쓸 때가 있는데
  이렇게도 쓴다고 한다... 실제는 {0}∪{1}이다.
• 연산 우선순위
  1. star
  2. concat
  3. union
• concat은 생략 가능하다
  AºB = AB

 

regular expression의 정의

기본 규칙

• {a}, $단, \ a \in \sum$
• ε
• ∅
  귀납적 규칙
• $(R_1 \cup R_2), \ 단, \ R_1, \ R_2$가 regular expression
• $(R_1R_2), \ 단, \ R_1, \ R_2$가 regular expression
• $(R_1^*), \ 단, \ R_1$가 regular expression

주의) ε와 ∅는 엄연히 다르다
    ε = 빈 문자열 -> |ε| = 1
    ∅ = 빈 집합 -> |∅| = 0

 

특수 표시들

$\sum^{}$ = 주어진 alphabet으로 만들 수 있는 모든 string의 집합
     $\sum^{}{???}\sum^{}$ = ???을 substring으로 가진 string의 집합
$R^+$ = $R R^$ = $R^$에서 ε 뺀거의 집합
     (적어도 하나 이상 뽑음)
∅ 에 관련된 표시
     R ∪ ∅ = R
     R º ∅ = ∅
     ∅\ = {ε}
ε 에 관련된 표시
     R ∪ ε ≠ R
     R º ε = R

 

예) $\sum = {0, \ 1}$ 이 있을때, ({0}∪{1}){0}* 이 나타내는 language는?
     - {0}∪{1} = {0, 1}
     - {0}* = {ε, 0, 00, 000, ...}
     - ({0}∪{1})º{0}* = {0, 1, 00, 10, 000, 100, ...}
     즉, 0 또는 1로 시작하고 그 이후엔 0만 나오는 string의 집합이다.

 

예) $\sum = {0, \ 1}$ 이 있을때, ($\sum \sum$)* 이 나타내는 language는?
     - $\sum \sum$ = {00, 10, 01, 11}
     - ($\sum \sum$)* = {ε, 00, 10, 0011, 011000, ...}
     즉, string의 길이가 짝수인 string의 집합

예) $\sum = {0, \ 1}$ 이 있을때, 1*(01+)* 이 나타내는 language는?
     - 1* = {ε, 1, 11, 111, ...}
     - 01+ = {0} º {1, 11, 111, ...} = {01, 011, 0111, ...}
     - (01+)* = {01011, 01101111, 011, ...}
     - 1*(01+)* = {101, 101101, 10101, 0101, 01101111, ...}
     즉, 0 다음에 1개 이상의 1이 오는 string의 집합이다.