Regular Expressions: 두 판 사이의 차이

youngwiki
← 이전 편집다음 편집 →
시각위키텍스트
37번째 줄: 37번째 줄:
   For all regular expressions R the language L(R) is a regular language.
   For all regular expressions R the language L(R) is a regular language.
이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이를 위해 아래의 명제들을 증명해야 한다:
이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이를 위해 아래의 명제들을 증명해야 한다:
[[파일:Figure 1. NFA for .png|섬네일|200x200픽셀|Figure 1. NFA for ]]
[[파일:Figure 1. NFA for .png|섬네일|200x200픽셀|Figure 1. NFA for <math>L(a)</math>]][[파일:Figure 2. NFA for.png|섬네일|200x200픽셀|Figure 2. NFA for <math>L(\epsilon)</math>]][[파일:Figure 3. NFA for.png|섬네일|200x200픽셀|Figure 3. NFA for <math>L(\empty)</math>]]
# [[파일:Figure 2. NFA for.png|섬네일|200x200픽셀|Figure 2. NFA for]]<math>\forall a \in \Sigma,\,\, L(a)</math> is a regular language.
# <math>\forall a \in \Sigma,\,\, L(a)</math> is a regular language.
# <math>L(\epsilon)</math> is a regular language.
# <math>L(\epsilon)</math> is a regular language.
# [[파일:Figure 3. NFA for.png|섬네일|200x200픽셀|Figure 3. NFA for]]<math>L(\empty)</math> is a regular language.
# <math>L(\empty)</math> is a regular language.
# <math>L(R1 \cup R2) = L(R1) \cup L(R2)</math> is a regular language.
# <math>L(R1 \cup R2) = L(R1) \cup L(R2)</math> is a regular language.
# <math>L(R1 \circ R2) = L(R1) \circ L(R2)</math> is a regular language.
# <math>L(R1 \circ R2) = L(R1) \circ L(R2)</math> is a regular language.
# <math>L(R1*) = (L(R1))*</math> is a regular language.
# <math>L(R1*) = (L(R1))*</math> is a regular language.
먼저, 명제 1, 2, 3들은 figure 1, 2, 3에 제시된 NFA를 통해 나타내어진다. 또한, 정규 언어들은 각 연산에 대해 닫혀(close)되어 있으므로, 명제 3, 4, 5번또한 성립한다고 할 수 있다.
먼저, 명제 1, 2, 3들은 figure 1, 2, 3에 제시된 NFA를 통해 나타내어진다. 또한, 정규 언어들은 각 연산에 대해 닫혀(close)되어 있으므로, 명제 3, 4, 5번또한 성립한다고 할 수 있다.
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>




2025년 9월 28일 (일) 23:39 판

상위 문서: Regular Languages

개요

정규 표현식(regular expression)은 문자열에서 특정한 패턴을 찾거나 치환·검증하기 위해 사용하는 표현식이다.

Formal Definition of Regular Expressions

정규 표현식 집합 ℛℰ는 알파벳 집합 Σ에 대해 아래의 닫힘 조건(closure conditions)을 만족하는 최소 집합을 의미한다:

  1. a∈ℛℰ,∀a∈Σ
  2. 빈 문자열 ϵ에 대해, ϵ∈ℛℰ
  3. 어떤 문자열도 포함하지 않는 공집합 ∅에 대해, ∅∈ℛℰ
  4. Union: If R1∈ℛℰ,R2∈ℛℰ, then (R1∪R2)∈ℛℰ
  5. Concatenation: If R1∈ℛℰ,R2∈ℛℰ, then (R1∘R2)∈ℛℰ
  6. Kleene Star: If R1∈ℛℰ, then (R1*)∈ℛℰ

이때 정규 표현식은 단순히 문자열(strings)이며, {∅,ϵ,(,),∪,∘,*}∪Σ라는 알파벳 집합 위에서 정의된다. 따라서, a∪b라는 정규표현식이 문자열로 해석되어 단순히 알파벳 a,∪,b의 조합인지, 혹은 정규표현식 a,b의 합집합으로 해석되는지는 맥락에 따라 달라진다.

Structural Induction for RE

어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다: 

1. P(a),∀a∈Σ 
2. P(ϵ),P(∅)

이를 바탕으로 두 ℛℰR1,R2에 대해 P(R1),P(R2)가 성립한다고 가정하면, 아래도 성립함을 보인다: 

1. P(R1∪R2)
2. P(R1∘R2)
3. P((R1*))

이 과정을 거치면 P(R)은 모든 정규 표현식 R에 대해 참이라는 결론을 얻을 수 있다.

The Language Denoted by a Regular Expression

아래는 정규 표현식 R이 나타내는 언어 L(R)을 귀납적으로 정의한 것이다:

  • L(a)={a} → 단일 문자열 { "a" }.
  • L(∅)=∅ → 아무 문자열도 없음.
  • L(ϵ)=ϵ → 오직 빈 문자열 하나만.
  • L(R1∪R2)=L(R1)∪L(R2)
  • L(R1∘R2)=L(R1)∘L(R2) → R1의 문자열과 R2의 문자열을 이어붙여 생성.
  • L(R1*)=(L(R1))* → R1이 만드는 문자열들의 0번 이상의 반복.

이때 아래와 같은 중요한 정리(Lemma)가 존재한다. 

 For all regular expressions R the language L(R) is a regular language.

이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이를 위해 아래의 명제들을 증명해야 한다:

Figure 1. NFA for L(a)
Figure 2. NFA for L(ϵ)
Figure 3. NFA for L(∅)
  1. ∀a∈Σ,L(a) is a regular language.
  2. L(ϵ) is a regular language.
  3. L(∅) is a regular language.
  4. L(R1∪R2)=L(R1)∪L(R2) is a regular language.
  5. L(R1∘R2)=L(R1)∘L(R2) is a regular language.
  6. L(R1*)=(L(R1))* is a regular language.

먼저, 명제 1, 2, 3들은 figure 1, 2, 3에 제시된 NFA를 통해 나타내어진다. 또한, 정규 언어들은 각 연산에 대해 닫혀(close)되어 있으므로, 명제 3, 4, 5번또한 성립한다고 할 수 있다.


Simplifying Operators

연산자 우선순위를 설정하여 괄호를 생략할 수 있는데, 그 순서는 ∪<∘<*(Kleene Star)와 같다. 또한 ∘ 기호를 생략하여 보통 문자열 처럼 붙여 쓸 수 있다. 따라서, 01*과 같은 정규 표현식은 0∘(1*)과 같다. 또한 아래는 복잡한 정규 표현식을 단순화한 예시이다. 

R≡(0∪(1∪(0(((0∪1)*)0))∪(1(((0∪1)*)1))))
R≡0∪1∪0(0∪1)*0∪1(0∪1)*1

위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.

각주

원본 주소 "https://junhoahn.kr/junyoung/index.php?title=Regular_Expressions&oldid=3609"