Regular Expression

○Regular Expression

 ▷alphabet Σ에 대한 Regular Expression을 다음과 같이 정의한다.

 ▷L(E): Regular Language (정규식이 표현하는 Language)

 

 ▶Base

  ▷E = Φ -> L(E) = Φ: empty Language이다.

  ▷E = λ -> L(E) = {λ}

  ▷E = a -> L(E) = {a}

 

 ▶Recursive Process (우선순위 대로)

  ▷Power: E = (E₁*) -> L(E) = L(E₁)*

  ▷Concatenation: E = (E₁ E₂) -> L(E) = L(E₁) L(E₂)

  ▷Union: E = (E₁ + E₂) -> L(E) = L(E₁) ∪ L(E₂)

 

 ▶Equivalence of Regular Expression

  ▷L(E₁) = L(E₂)이라면, E₁과 E₂는 equivalent하다.

  ▷다른 정규식이지만, 나타내는 Language가 같다.

 

 ◎예시들

  ▷짝수/홀수의 alphabet

  ▷1개 / 2개의 alphabet 포함.

  ▷substring을 포함 (ex) 11)

  ▷substring을 미포함 (ex) 11)