정규 표현

정규 문법 표현하는 방법

해당 글은 정규 문법의 연산 순서의 양줄이기 버전입니다
정규 문법을 가장 잘 표현 할 수 있는 방법에 대해 알아보자!

위의 정의에서 연산자의 우선 순위는 *(클리니 클로저) > •(접속) > +(합집합)이다.
사칙 연산과 동일하게 왼쪽 결합 법칙 이 적용 된다

예제. 다음 정규 표현의 연산 순서는?

앞서 말한, 연산자 우선 순위와 왼쪽 결합 법칙을 이용하면 위와 같은 연산 순서를 가지게 된다.
이렇게 보니, 사칙 연산과 동일하다 생각해도 될 듯하다

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

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로 만들 수 있는 모든 문자열의 집합이다.

좀 더 연습을 하자면, (a+b)*abb는 a와 b로 만들어지는 모든 문자열 중에서 abb로 끝나는 문자열의 집합이다

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

Σ = {0, 1, a, b}에 대해 0 * ( 0 + 1) 이 정규 표현인지 아닌지를 판단하고 정규 표현이라면 생성되는 언어를 설명해보자.

앞서 배운, 정규 표현 규칙을 활용해서 문제를 풀면 된다.

기본 정규식은 빈 집합(∅), 빈 문자열(ε) 및 알파벳 집합 Σ의 단일 기호이다.
즉 Σ = {0, 1, a, b}이므로 0, 1 ,a,b는 실제로 정규 표현식이다.

3번 규칙에 의해, 0과 1은 정규 표현이고, 0이 정규 표현이므로, 0*도 정규표현이다.
같은 방법으로 0과 1이 정규 표현이므로,1번에 의해 (0 + 1)도 정규표현이다.

(0+1)이 정규 표현이므로 당연히 (0+1)*도 정규표현이다.
또한, 0*와 (0 + 1)*가 정규 표현이므로 귀납 단계 2번에 의해 최종적으로 0 * ( 0 + 1)도 정규 표현식이다.

이 언어는 ε을 포함하여 0과 1로 만들 수 있는 모든 문자열의 집합(단 1로 시작하는 문자열은 생성하지 않는다)이다.

예제 3.22 정규표현으로 나타내기

다음과 같은 문법에서 ident를 정규 표현으로 나타내자보자

<ident> ::= (<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 그리고 언더바가 되며 길이는 제한이 없는 문 자열이다.

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>