이산수학 정규식과 정규문법

이산수학: 형식언어와 오토마타2 - 정규식과 정규문법

문자열 표기법

• I : 기호(symbol)들의 집합(알파벳)
• I* : 집합 I의 기호들을 결합하여 만들어지는 유한 크기를 갖는 모든 문자열의 집합
• λ : 공 문자열(empty string)
• αβ : 문자열 α와 문자열 β의 연결 (concatenation)
• α+β : 두 문자열 α, β의 합집합 (+는 ∪로도 표시한다)
• (α)* : 문자열 α가 유한 개수만큼 반복되어 만들어지는 문자열
  λ ∈(α)*, (α)* ≡ α*
  

---

정규식 (reqular expression)

• I : 기호들의 집합(알파벳)
• I 에서 정의되는 정규식은 다음과 같이 재귀적으로 정의된다
  1. 공문자열 λ는 정규식이다
  2. α∈I 라면 α는 정규식이다
  3. α과 β가 각각 정규식이면 αβ도 정규식이다
  4. α과 β가 각각 정규식이면 α+β도 정규식이다
  5. α가 정규식이면 α*도 정규식이다

---

정규 집합 (reqular set)

• I* 으로 표현

• 정규식으로부터 만들어지는 모든 문자열들을 정규 집합이라고 함

  예시)
  I={a, b, c} 일때, 다음의 정규식으로 만들어지는 정규집합 I*를 구하여라
  a* → I* = {λ, a, aa, aaa, aaaa, ...}
  a(b+c) → I* = {ab, ac}
  ab(bc)* → I* = {ab, abbc, abcbcbc, ...}

• 정규 문법: 정규 문법은 정규식으로 표현될 수 있으며 정규 문법에 의해서 생성되는 언어는
  정규식에 의해서 만들어지는 정규 집합과 동일하다