정규 문법을 정규 표현으로 변경

정규 문법을 정규 언어로 변경시 중간 기점으로 정규 표현을 사용하면 쉽게 정규 문법으로 변경이 가능한다.

정규문법을 정규표현으로 변경시 아래 두가지 형태를 알아두면 편하게 정규 수식으로 변경이 가능하다.

(공식 1) 다음과 같은 유도를 보일 때

A -> A α | β

이를 정규 수식으로 바꾸어 보자.

(풀이) A 는 A α 혹은 β 로 유도될 수 있으므로

• A -> β 로 유도되면 β 를 만들어 낼수 있고

  

• A -> A α 로 유도된다면

  

• A -> β 로 유도되면 β α 를 만들어 낼수 있고

  

• A -> A α 로 유도된다면

  

• A -> β 로 유도되면 β α α 를 만들어 낼수 있고

  

• ...

이 문법으로 만들 수 있는 스트링은 β 로 시작하고 α 를 0 개 이상 만들 수 있는 스트링을 인식할 수 있다.

정규 표현을 나타내면

A = A α + β = β · α^*

(공식 2) 다음과 같은 유도를 보일 때

A -> α A | β

이를 정규 수식으로 바꾸어 보자.

(풀이)

• A -> β 로 유도된다면 β 를 만들 수 있고

  

• A -> α A 로 유도된다면

  

• A -> β 로 유도된다면 α · β 를 만들 수 있고

  

• A -> α A 로 유도된다면

  

• A -> β 로 유도된다면 α ·α · β 를 만들 수 있고

  

• ...

이는 0 개 이상의 α 로 시작하고 , β 로 종료하는 스트링을 인식하는 문법이다.

정규 표현을 나타내면

A = α · A + β = α^* ·β

(보기) 정규 표현을 이용하여 다음 정규 문법이 생성하는 언어를 구해보자.

G=( { A } , {a,b,c} , P , A )

P: A -> aA | bA | c

(풀이) 유도 규칙을 정규 표현으로 나타내면

A = aA + bA + c
  = (a+b)A + c

위 식은 A = α A + β 형식이므로

A = (a + b)^* · c

이는 a ,b 가 임의 수 만큼 올수 있고 마지막은 c 로 끝나는 스트링을 인식할 수 있는 문법이다.

이 문법이 생성하는 언어는

L(G)={ (a + b)ⁿ · c | n >=0 } ###

(유제1) 정규 표현을 이용하여 다음 정규 문법이 생성하는 언어를 구해보자.

G=( {A,B} , {a,b}, P, A)

P: A -> aB
   B -> bB | b

(유제2) 정규 표현을 이용하여 다음 정규 문법이 생성하는 언어를 구해보자.

G=( {S,R},{a,b},P,S)

P: S -> aS | bR | ε
   R -> aS