Regular Expressions: 두 판 사이의 차이

youngwiki
← 이전 편집다음 편집 →
시각위키텍스트
편집 요약 없음
45번째 줄: 45번째 줄:
# <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번또한 성립한다고 할 수 있다.


===Simplifying Operators===
===Simplifying Operators===
52번째 줄: 51번째 줄:
  <math>R \equiv 0 \cup 1\cup 0(0\cup1)*0\cup1(0\cup1)*1</math>
  <math>R \equiv 0 \cup 1\cup 0(0\cup1)*0\cup1(0\cup1)*1</math>
위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.
위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.
<math></math>
 
==Constructing a RE from a NFA==
모든 정규 언어는 정규표현식으로 표현될 수 있다. 즉, NFA가 주어지면 반드시 동치인 정규표현식이 존재한다. 이는 아래와 같은 정리(Lemma)를 통해 나타낼 수 있다:
If L is a regular language, then L = L(R) for some regular expression R.
이를 증명하는 방법은 상태 제거 절차(state elimination procedure)이며, 이는 NFA의 상태들을 하나씩 제거하면서, 그 상태를 통과하는 경로들을 정규표현식으로 바꿔가며 단순화하는 것이다. 이때 일반적인 NFA는 각각의 전이(transit)에 해당하는 화살표가 단일 문자(혹은 <math>\epsilon</math>)으로 라벨링되어 있다. 하지만 상태를 제거하다 보면, 두 상태를 연결하는 경로가 단일 문자가 아니라 정규표현식 전체로 표현되는 경우가 생기며, 이를 더욱 쉽게 나타낼 수 있도록 GNFA(Generalized NFA)라는 개념을 도입할 수 있다. 즉, GNFA는 “전이가 단일 문자 대신 정규표현식으로 라벨링된 NFA”를 의미한다.
<math></math>
<math></math>
<math></math>
<math></math>

2025년 9월 29일 (월) 00:52 판

상위 문서: 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을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.

Constructing a RE from a NFA

모든 정규 언어는 정규표현식으로 표현될 수 있다. 즉, NFA가 주어지면 반드시 동치인 정규표현식이 존재한다. 이는 아래와 같은 정리(Lemma)를 통해 나타낼 수 있다: 

If L is a regular language, then L = L(R) for some regular expression R.

이를 증명하는 방법은 상태 제거 절차(state elimination procedure)이며, 이는 NFA의 상태들을 하나씩 제거하면서, 그 상태를 통과하는 경로들을 정규표현식으로 바꿔가며 단순화하는 것이다. 이때 일반적인 NFA는 각각의 전이(transit)에 해당하는 화살표가 단일 문자(혹은 ϵ)으로 라벨링되어 있다. 하지만 상태를 제거하다 보면, 두 상태를 연결하는 경로가 단일 문자가 아니라 정규표현식 전체로 표현되는 경우가 생기며, 이를 더욱 쉽게 나타낼 수 있도록 GNFA(Generalized NFA)라는 개념을 도입할 수 있다. 즉, GNFA는 “전이가 단일 문자 대신 정규표현식으로 라벨링된 NFA”를 의미한다.

각주

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