RE를 NFA로 변환

Question

RE 조합 0 + 1을 표시하는 올바른 방법은 어느 것입니까? 나는이 두 가지 방법을 보았지만 둘 다 맞다고 생각합니다. 둘 다 정확하다면 왜 복잡한 일을해야합니까? 당신이 언급 한 바와 같이

Answer 1

그들은 모두 정확합니다.

첫 번째 규칙은 일련의 표준 규칙을 사용하여 생성 된 것처럼 보입니다.이 경우 잔인 함 (바보처럼 보이기는하지만)이 더 복잡한 경우에는 전체 규칙을 유지하는 것보다 쉬운 규칙을 따르는 것이 더 쉽습니다 당신의 머리에서 그리고 동등한 NFA를 처음부터 쓰십시오.

일반적으로 NFA는 하나의 최종 상태 (분명히 이미 하나의 시작 상태 만 있음)를 갖도록 재 작성 될 수 있습니다.

그런 다음이 양식의 두 개의 NFA가 결합 될 때 허용되는 언어가 개별적으로 수락되는 언어의 결합 인 방식으로 결합 될 수 있습니다. 이는 정규 표현식의 (+)에 해당합니다. 이러한 방식으로 NFA를 결합하려면 간단하게 시작 상태로 작동 할 새 노드를 만들고 두 NFA의 시작 상태로 ε 전환으로 연결하십시오.

그런 다음 단일 최종 상태에서 NFA를 깔끔하게 종료하기 위해 (원하는 경우 다른 NFA에 대해이 NFA를 재귀 적으로 사용할 수 있도록) 통합 최종 상태 및 ε- 이전 최종 상태 (최종 상태를 잃는)를 연결합니다. 위의 일반 규칙 사용

, 제 도면에 도달하기 쉽다 (두 NFA 쌍이 UNION을 함께 0을 일치 제 다른 1) -은 이러한 간단한 이후 제 상식 통해 도달하기 쉽다 정규 표현식 ;-)

Answer 2

첫 번째 구문은 일반적인 NFA 클래스의 확장 인 전자 이동을 사용하는 NFA 클래스에 속합니다. 전자 이동은 입력이 필요없이 전환을 수행 할 수있는 기능을 제공합니다. 전이 함수의 경우, 전이 상태에서만 사용 가능한 주어진 상태에서 도달 할 수있는 상태 집합을 계산하는 것이 중요합니다. 분명히 전자 이동을 추가하면 NFA가 비표준 언어를 허용하지 않으므로 결국 NFA 및 DFA와 동등합니다.

전자 이동을 사용하는 NFA는 Thompson의 생성 알고리즘에 의해 일반 표현식에서 자동 완성을 만드는 데 사용됩니다. regexs에서 자동 생성을 구성하는 표준 방법을 제공합니다.