형식언어와 오토마타.03.01
상위 문서: {{ item.title }} -
cs
REGULAR EXPRESSIONS
- CHAPTER 3. REGULAR LANGUAGES AND REGULAR GRAMMARS
- 3.1 REGULAR EXPRESSIONS
- 챕터 3. 정규 언어와 정규 문법
- 3.1 정규 표현
According to our definition, a language is regular if there exists a finite accepter for it.
- finite accepter가 있는 언어는 정규 언어이다.
정규 표현(Regular Expression)
DEFINITION 3.1
Let be a given alphabet. Then
- and are all regular expressions. These are called primitive regular expressions.
- If and are regular expressions, so are , and ().
- A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).
주어진 알파벳 에 대하여,
- 그리고 는 모두 정규 표현이며, 기본 정규 표현(primitive regular expressions)이라 부른다.
- 가 정규 표현이면,
- 도 정규 표현이다.
- 도 정규 표현이다.
- 참고: ` ⋅ `는 concatenation 이다.
- 도 정규 표현이다.
- 도 정규 표현이다.
- 기본 정규 표현에 2번 규칙을 유한한 횟수만큼 적용해서 나오는 문자열은 모두 정규 표현이다.
DEFINITION 3.2
The language denoted by any regular expression is defined by the following rules.
- is a regular expression denoting the empty set,
- is a regular expression denoting ,
- For every , a is a regular expression denoting .
If and are regular expressions, then- ,
- ,
- ,
- .
정규 표현 r로 표현되는 언어 은 다음의 규칙들로 정의할 수 있다.
- 재귀를 종료하기 위한 규칙
- 1 . 은 공집합을 의미하는 정규 표현이다.
- 2 . 는 를 의미하는 정규 표현이다.
- 3 . 의 원소인 에 대해, 는 를 의미하는 정규 표현이다.
- 재귀적으로 을 간단하게 변환하는 규칙.
- 4 . ,
- 5 . ,
- 6 . ,
- 7 . .
두 정규 표현이 같은 언어를 표현하는 경우 동치 관계에 있다고 한다.
예제 3.2
Exhibit the language in set notation.
언어 를 집합 형식으로 나열하라.
참고
- 우리에게 익숙한 perl, javascript 정규표현식과 비교해 본다면?
*
은 똑같은 의미를 갖는다.- 는 concat이므로 와 같다. 즉, 무시해도 된다.
- 이므로
[ab]
와 같다. - 따라서 이 문제는
^a*[ab]$
와 같다.
예제 3.3
에 대한 정규 표현 은 다음 언어를 표현한다.
이번에도 우리에게 익숙한 perl, javascript 정규표현식으로 표현해 보자.
- 는
[ab]*
이다. - 는
(a|bb)
이다. - 그러므로
^[ab]*(a|bb)$
이다.- 캡처 그룹을 안 쓴다면
^[ab]*(?:a|bb)$
.
- 캡처 그룹을 안 쓴다면
예제 3.4
은 짝수개 a 다음에 홀수개의 b가 오는 모든 문자열들로 이루어지는 언어를 표현한다.
이번에도 우리에게 익숙한 perl, javascript 정규표현식으로 표현해 보면…
^(aa)*(bb)*b$
- 재미있게도 원래 정규 표현 과 똑같은 형태의 정규표현식이 나온다.