정규식을 NFA 변환 테이블로 변환

Question

언어는 중요하지 않지만 정규식을 NFA 테이블로 변환하는 방법을 알아야합니다. 예를 들어 "(ab) * + ba"는
으로 바뀝니다. T | a | b |^
0 | N | 1 | 2
1 | 3 | N | N
2 | 4 | N | 3
3 | N | N | N
4 | N | 2 | N

누군가가 올바른 방향으로 나를 가리 키거나 도움이 될 수 있다면 어떻게하면 좋을지 보여 주시면 감사하겠습니다.

편집 : 나는 한 번 봐했다 :
http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html을하지만, 난 여전히 가장 바깥 쪽 작업을 찾을 수 있습니다,이

Answer 1

먼저 프로그래밍하는 방법의 아이디어를 얻을 수 없습니다. 귀하의 예에서는 +입니다. +이 있으면 왼쪽에있는 것 또는 오른쪽에있는 것 중 하나를 수락 할 수 있음을 의미합니다.

Q s Q' 
q0 - M1 
q0 - M2 

우리는 우리의 출발점으로 q0을 가지고 우리는 LHS에 의해 생성 된 문자열을 받아 기계를 대표하는 M1 및 M2를 사용하여 우리는 다음과 같이 전환을 빈 (람다, 또는 엡실론)를 사용하여 NFA이 인코딩 할 수 있습니다 우리의 정규 표현식의 각각 RHS. q0을 람다/엡실론 - 비어있는 전환시에 M1과 M2으로 전환 할 때, 우리는 비대칭 적으로 어떤 경로가 다운되는지를 선택한다는 의미입니다. 전환은 q0에서 시작하여 M1 및 M2의 초기 상태가됩니다.

이제 우리는 LHS와 RHS 각각에 대해 반복적으로 프로세스를 반복합니다. 우리는 더 간단하기 때문에 RHS부터 시작할 수 있습니다. 가장 바깥 쪽의 연산은 연결 (기호 a 및 b)입니다. 병합은 표현하기 간단 여기

Q s Q' 
q2 - M3 
M3 - M4 

, q2 이전부터 M2 및 M3 및 M4의 초기 상태 대표 그대로의 미의 연접 각각 LHS와 RHS 동의 미결정 기계 a 및 b. q2을 M3으로 변환하면 M3의 초기 상태로 전환됩니다. M3이 M4으로 전환되면 M3의 모든 수락 상태를 M4의 초기 상태로 전환하는 것을 의미합니다.

재귀 적으로 진행하려면 a 및 b의 기계가 필요합니다.

q가 초기 상태입니다

Q s Q' 
q x q' 

, x이 상징이며 q'가 받아들이는 상태 :이 두 형태가있다.그래서 우리가 얻을 :

Q s Q' 
q3 b q4 (q3 initial, q4 accepting) 

하고 우리는이 재귀 지점의 바닥에 충돌하고 우리가 정의한 콘크리트 기계를 기반으로 전환 테이블에 구체적인 항목을 생성, 백업 단계 수

Q s Q' 
q5 a q6 (q5 initial, q6 accepting) 

.

Q s Q' 
q2 - M3 
M3 - M4 

그리고 지금 우리는 M3 및 M4 모습 같은, 그래서 우리는 대체 할 수 있습니다 알고 :

Q s Q' 
q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 (q2 initial, q6 accepting) 

지금 우리가 + 작업에서 LHS을 할 준비가되어 우리는이 있었다. 가장 바깥 쪽 작업은 *입니다. NFC에서 이러한 문제를 처리하는 방법은 다음과 같습니다.

Q s Q' 
q7 - M5 
M5 - M5 

이제 다음 작업 인 연결을 고려해 보겠습니다. 우리는 이미이 덮여하고 우리는 우리가 얻을 알고 :

Q s Q' 
q8 - M6 
M6 - M7 

이제 우리는 a 및 b이 필요합니다. 우리는이 모두를 다시 제자리에 갖다 놓는다

Q s Q' 
q9 a q10 

및

Q s Q' 
q11 b q12 

: 다시 말하지만, 우리는 같은이 모습을 알고

다음

Q s Q' 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 (q8 initial, q12 accepting) 

우리는 149) 클린의 별 (Kleene star 수행

Q s Q' 
q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q8 initial, q8 and q12 accepting) 

을

마지막으로, 모든 규칙을 하나의 큰 trans로 결합합니다 반복 테이블 :

Q s Q' 

q0 - q2 
q0 - q7 

q2 - q3 
q3 b q4 
q4 - q5 
q5 a q6 

q7 - q8 
q8 - q9 
q9 a q10 
q10 - q11 
q11 b q12 
q12 - q8 (q0 initial, q6, q8 and q12 accepting) 

따라서 임의의 정규 표현식에 대해 NFA를 재귀 적으로 생성 할 수 있습니다. 결과 NFA는 일반적인 경우에 불필요한 상태가되지만 NFA 최적화는 민감한 주제입니다. 언제든지이 (또는 모든) NFA를 가져 와서 알려진 알고리즘을 사용하여 DFA로 변환 한 다음 알려진 알고리즘을 사용하여 최소화 할 수 있습니다. 그렇다면이 패딩 된 NFA보다 훨씬 더 큽니다.