정규 언어, 정규 문법, 유한 오토마타의 동치 관계

정규 언어, 정규 문법, 유한 오토마타의 동치 관계

1. 전체 문법이 주어지면 문법으로 부터 토큰들을 분리해내고 이 토큰들을 정규 문법으로 표현
2. 토큰에 대한 정규 문법을 정규 표현으로 표시.
3. 이 정규 표현을 인식하는 인식기를 만들면 을 주면 언어가 주어지면, 이를 정규표현으로 변환
4. 정규표현을 인식하는 NFA을 구성, NFA를 DFA로 변환, DFA를 최소화 하면 어휘 분석기 를 만들 수 있음

정규 문법, 정규 표현, 유한 오토마타의 관계가 서로 동치관계 임을 증명

1. 정규문법 ⇒ 정규표현
2. 정규표현 ⇒ 유한오토마타
3. 유한 오토마타 ⇒ 정규문법

정규문법 ⇒ 정규표현으로변환

정규표현에의해서 정의된 문법G에 의해 생성 되는 언어 L(G)가 무엇인지를 알기 위해서는, 정규 문법을 정규 표현으로 변환

정규 문법을 계수(coefficient)가 정규 표현으로 구성된 방정식인 정규 표현 방정식(regular expression equation)으로 바꾸고 정규 표현 방정식에서 해(solution) 를 구함

정규 표현 방정식으로부터 해를 구하는 방법

[알고리즘3-3]정규문법 ⇒정규표현으로 변환 알고리즘

[방법]
(1) 정규 문법으로부터 정규 표현 방정식을 만든다.
(2)정규 표현 방정식 중 X=αX+β 형태를 찾아 X=α* β로 변환한다.
(3) 시작 기호로부터 출발하여 다른 방정식들을 대입한다.

계산 결과에 X= αX + β 형태 의식이 나타나면X=α* β로 변환하면,정의된 정규 문법 G로부터 생성 되는 정규 언어 L(G)를 나타내는 정규 표현이 된다.

정규표현 ⇒유한오토마타로변환

• 정규 표현의 정의에 있는 각각을 받아들이는 ε–NFA를 구성
  

예제

[예제 3-56] 정규 문법 G = ({S, A, B}, {a, b}, P, S)가 다음과 같을 때 G로부터 생성되는 L(G)를 정규 표현으로 나타내보자

더 이상 X = αX + β 형태가 없고 시작 기호가 S이므로 (1)번 식부터 시작

• S = aA + bS
  • (aS + bB) + bS ( (2)번 식 대입)
  • aaS + abB +bS
  • aaS + ab(a+b)* +bS ( (4)번 식 대입)
  • (aa+b)S + ab(a+b)*
  • 그런데 이 식은 X = αX + β 형태이므로 S = (aa +b)*ab(a+b)*

[예제 3-57] 정규 문법 G = ({S, A, B}, {a, b}, P, S)가 다음과 같을 때 G로부터 생성되는 L(G)를 정규 표현으로 나타내보자

[예제 3-58] 정규 표현을 받아들이는 유한 오토마타 만들기 1

[예제 3-59] 정규 표현을 받아들이는 유한 오토마타 만들기 2

[알고리즘 3-4] 유한 오토마타로 부터 정규 문법으로 변환

[예제 3-61] 유한 오토마타를 정규 문법으로 변환하기

• [예제 3-60]의 결과인 유한 오토마타를 정규 문법 G로 변환해보자.
  

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