문법의 표기법 1 (정규 표현)

정규 표현: 정규 문법을 가장 잘 표현할 수 있는 방법

 

기본 단계

- 알파벳 Σ에 대해서

- 기본 단계 -  Ф, ε, a(알파벳 문자) ∈ VT 는 모두 정규 표현

- 귀납 단계 - 만일 r, s가 정규 언어 Ln, Ls를 표현하는 정규 표현이라 하면

    (1) (r) + (s)는 Ln ∪ Ls를 나타내는 정규 표현이다

    (2) (r) • (s)는 Ln • Ls를 나타내는 정규 표현이다

    (3) (r)*는 (Lr)*를 나타내는 정규 표현이다

- 위의 정의에서 연산자의 우선 순위(precedence)는 * > • > +

- 연산자 *(클리니 클로저)가 우선 순위가 가장 높고

- 연산자 • (접속)이 두번째 우선순위

- 연산자 + (합집합)가 가장 낮은 우선 순위, 왼쪽 결합 법칙을 가짐(왼쪽부터 한다는 것)

- 연산자 우선 순위와 결합 법칙이 결정 되면 괄호를 사용하지 않아도 됨

 

정규 표현에 의해 생성되는 언어

ex.
Σ = {0, 1}에 대해 정규 표현이 나타내는 언어는?

1. 0 + 1 > {0, 1}

2. (0 + 1)0 > {00, 10}

3. 0* > { ε, 0, 00, 000 ...}

4. (0 + 1)* > { ε, 0, 1, 00, 01, 10, 11, 000, ...} ε을 포함하여 0과 1로 만들 수 있는 모든 문자열의 집합

 

ex.

(a+b)*abb

a와 b로 만들어지는 모든 문자열 중에서 abb로 끝나는 문자열의 집합

 

정규 표현인지 판단하고 생성되는 언어 구하기

Σ = {0, 1, a, b}에 대해 정규 표현인지 아닌지를 판단하고 생성되는 언어를 설명

0*(0 + 1)*

기본 단계에 의해 0과 1은 정규 표현, 귀납 단계 1번에 의해 (0 + 1)도 정규 표현

(0 + 1)번이 정규 표현이므로 귀납 단계 3번에 의해 (0 + 1)*도 정규 표현

0*, (0 + 1)* 둘 다 정규표현이니 귀납 단계 2번에 의해 0*(0 + 1)*도 정규 표현

 

이 언어는 ε을 포함하여 0과 1로 만들 수 있는 모든 문자열의 집합

(앞에 0이 여러개 붙을 수 있지만, (0 + 1)* 자체로 그 경우를 포함함)

 

 

정규 표현으로 나타내기

ident라는 문법 규칙이 주어졌을 때, 정규 표현으로 바꾸기 (::=는 문법 정의)

<ident> ::= ( <letter> | _ ) { <letter> | <digit> | _ }     // 첫 글자는 letter나 _, 이후는 letter, digit,  _ 중 하나로 길이제한 없음({})

<letter> ::= a | ... | z

<digit> ::= 0 | 1 | ... | 9

 

정규 표현

(l + _)(l + d + _)*

단, l -> a | ... | z 이고 d -> 0 | 1 | ... | 9

ident는 첫 자가 영문자 소문자 a, ..., z, _로 시작하고 두번째 자부터는 영문자 소문자 a, ..., z, 숫자 0, 1, ... 9 그리고 _가 되며,

길이는 제한이 없는 문자열

α β γ

정규 표현의 대수학적 성질 (f는 공집합, ε랑은 다름. ε는 빈 문자열 "")

- ( α + β ) + γ =  α + ( β  + γ )     // +에 대한 결합 법칙

- ( αβ)γ = α(βγ)                          // 접속에 대한 결합 법칙

- α + β = β +  α                          // +에 대한 교환 법칙

- α + α = α                                 // +는 합집합임, 중복된 표현은 의미가 없음

- α( β  + γ ) = αβ + αγ               // 분배 법칙

- ( β  + γ )α = βα + γα               // 분배 법칙

- α + f = α

- εα = α = αε                             // 접속 연산의 항등원

- α* = ε + αα*                            // 풀어서 정리하면 똑같은 식임

- = ( ε + α )*

- (α*)* = α*

- α* + α = α*

- ( α + β )* = ( α*β* )*

- ( α + β )* = ( α* + β* )*

- α* + α+ = α*

- f* = ε

- ε* = ε

- ( α + β )* = α* + β*

- ( γα + γ )*γ = γ( γα + γ )*