정규 문법을 유한 자동 바꾸기

(보기1) 다음 정규 문법을 정규 수식으로 바꾸어 보자.

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

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

(풀이) 이 문법을 정규수식으로 바꾸어 보면 ,

A = aB ------ 1
B = bB+c ---- 2

2 식은 A = α A + β 형태의 정규 수식이므로 b^*c 이므로 이 식을 1 식에 대입하면

A=a$b^*$c

즉 이 문법은 a 로 시작하고 b 는 0 개 이상 무한정올수 있고 반드시 c 로 끝나는 스트링을 인식하는 문법이다. 즉 ab , abc , abbc , abbbc , abbbbbc , ...###

(보기2) 보기 1 의 정규 문법을 오토마타 로 바꾸어 보자.

(풀이) 정규 문법을

G=(N,T,P,S)

오토마타(유한 오토마타)

M=(Q, Σ , δ , q₀ , F)

로 변경하는 작업은

• V_N 에서 종료 상태 C 를 추가 Q={ A , B , C}
• 입력 기호는 V_T 는 Σ 와 같음 Σ = { a , b , c}
• δ 는 P 와 같지만 표현 방법이 조금 다름

  매핑 함수(mapping function) δ

  A->aB 표현은 δ(A,a) = B
  B->bB 표현은 δ(B,b) = B
  B->cC 표현은 δ(B,c) = C
  

• q₀ 는 S 와 동일
• F 는 종료 상태 F={C}. 종료상태는 한 상태 이상 가능

이 mapping 함수로 상태도를 그려보면

상태도에서 동그라미 두개의 의미는 해당 상태가 종료 상태임을 의미한다. 이 상태도 의미는 보기 1 에서의 ab^*c 와 동일하다.###

(유제) 다음 정규 문법을 유한 자동으로 바꾼후 상태도를 그려서 두 개의 의미가 동일한가를 확인하라.

G=( {S,A} , { l(소문자 엘) , d , b} , P , S)

P: S -> lA 
   A -> lA | dA | b