Regular Expressions: 두 판 사이의 차이
| 34번째 줄: | 34번째 줄: | ||
* <math>L(R_1 \circ R_2) = L(R_1) \circ L(R_2)</math> → R1의 문자열과 R2의 문자열을 이어붙여 생성. | * <math>L(R_1 \circ R_2) = L(R_1) \circ L(R_2)</math> → R1의 문자열과 R2의 문자열을 이어붙여 생성. | ||
* <math>L(R_1*) = (L(R_1))*</math> → R1이 만드는 문자열들의 0번 이상의 반복. | * <math>L(R_1*) = (L(R_1))*</math> → R1이 만드는 문자열들의 0번 이상의 반복. | ||
이때 아래와 같은 중요한 정리(Lemma)가 존재한다. | |||
For all regular expressions R the language L(R) is a regular language. | |||
이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이는 아래와 같은 단계를 거친다. | |||
===Simplifying Operators=== | ===Simplifying Operators=== | ||
2025년 9월 28일 (일) 23:25 판
상위 문서: Regular Languages
개요
정규 표현식(regular expression)은 문자열에서 특정한 패턴을 찾거나 치환·검증하기 위해 사용하는 표현식이다.
Formal Definition of Regular Expressions
정규 표현식 집합 는 알파벳 집합 에 대해 아래의 닫힘 조건(closure conditions)을 만족하는 최소 집합을 의미한다:
- 빈 문자열 에 대해,
- 어떤 문자열도 포함하지 않는 공집합 에 대해,
- Union: If , then
- Concatenation: If , then
- Kleene Star: If , then
이때 정규 표현식은 단순히 문자열(strings)이며, 라는 알파벳 집합 위에서 정의된다. 따라서, 라는 정규표현식이 문자열로 해석되어 단순히 알파벳 의 조합인지, 혹은 정규표현식 의 합집합으로 해석되는지는 맥락에 따라 달라진다.
Structural Induction for RE
어떤 성질 P(R)이 모든 정규 표현식 R에 대해 성립함을 보이고 싶다면 먼저, 아래와 같은 기본 케이스를 규정해야 한다:
1. 2.
이를 바탕으로 두 에 대해 가 성립한다고 가정하면, 아래도 성립함을 보인다:
1. 2. 3.
이 과정을 거치면 P(R)은 모든 정규 표현식 R에 대해 참이라는 결론을 얻을 수 있다.
The Language Denoted by a Regular Expression
아래는 정규 표현식 R이 나타내는 언어 L(R)을 귀납적으로 정의한 것이다:
- → 단일 문자열 { "a" }.
- → 아무 문자열도 없음.
- → 오직 빈 문자열 하나만.
- → R1의 문자열과 R2의 문자열을 이어붙여 생성.
- → R1이 만드는 문자열들의 0번 이상의 반복.
이때 아래와 같은 중요한 정리(Lemma)가 존재한다.
For all regular expressions R the language L(R) is a regular language.
이를 증명하기 위해서는 구조적 귀납법(Structural Induction)을 사용하며, 이는 아래와 같은 단계를 거친다.
Simplifying Operators
연산자 우선순위를 설정하여 괄호를 생략할 수 있는데, 그 순서는 (Kleene Star)와 같다. 또한 기호를 생략하여 보통 문자열 처럼 붙여 쓸 수 있다. 따라서, 과 같은 정규 표현식은 과 같다. 또한 아래는 복잡한 정규 표현식을 단순화한 예시이다.
위의 예시는 사람이 읽기에 훨씬 편하도록 R을 만든 것이다. 이는 연산자 우선순위 규칙과 괄호 생략 규칙을 도입한 이유이다.
