Regular Expressions: 두 판 사이의 차이

youngwiki
← 이전 편집다음 편집 →
시각위키텍스트
19번째 줄: 19번째 줄:
어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다:
어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다:
  1. <math>P(a), \forall a \in \Sigma</math>  
  1. <math>P(a), \forall a \in \Sigma</math>  
  2. <math>P(\epsilon), \P(\empty)</math>
  2. <math>P(\epsilon), P(\empty)</math>
이를 바탕으로 두 <math>\mathcal{RE}\,\, R_1, R_2</math>에 대해 <math>P(R_1), P(R_2)</math>가 성립한다고 가정하면, 아래도 성립함을 보인다:
이를 바탕으로 두 <math>\mathcal{RE}\,\, R_1, R_2</math>에 대해 <math>P(R_1), P(R_2)</math>가 성립한다고 가정하면, 아래도 성립함을 보인다:
  1. <math>P(R_1 \cup R_2)</math>
  1. <math>P(R_1 \cup R_2)</math>

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

상위 문서: 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번 이상의 반복.

각주

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