2
정규 표현식에서 NFA-s를 만드는 방법을 이해하려고 시도하고 있지만 실제로는 엡실론 전환과 혼동합니다. 내 교과서에이 예가 있지만 엡실론 전환이 사용되는 이유와 사용시기를 어떻게 알 수는 없습니다. 그들이 편리 할 때 일반적으로 espilon-전환에NFA에서 엡실론 전환이 사용되는 이유는 무엇입니까?
A
답변
1
이 사용됩니다. 예를 들어 정규 표현식에서 NFA를 구성 할 때 표현식의 일부에 해당하는 오토 마톤의 작은 부분을 구성하여 시작합니다. 연결하려면 전환을해야합니다. 그러나 거기에 읽을 기호가 없다면 엡실론 전환이이를 수행하는 간단한 방법입니다. 그들은 결코 필요하지는 않지만, 당신은 항상 그것들없이 해결책을 찾을 수 있습니다.
예를 들어, 교과서에 설명 된 알고리즘을 적용하면됩니다. 언제 사용할지 알려줍니다.
엡실론이
- 에서 1~2 아마위한 부품 접속 전환 (A | B) *과 교류 위한
- 1-> 5 및 8> 1 아마 * 기인
- 5-> 6 및 5-> 7은 대체로 | NFA 쌍이에서
0
엡실론 - 전환은 선택 또는 정규 표현식에서 분리 또는 조합의 자연스러운 표현이다. 즉, (원하는 표기에 따라 또는 r | s 또는 r U s) r + s 같은 정규식 자연스럽게 NFA 두 독립적 NFA 쌍이, r 용과 s 하나 이루어진로 표현된다 다음으로 전자 천이를 이용한 접합 :
e
----->q0----->(r)
|
| e
|
V
(s)
더 복잡한 방법으로 상태를 연결하는 데 사용하는 경우 효과가 설명하기가 쉽지 않거나 자연스럽지 않을 수 있지만 기본적으로 이러한 전환을 사용하면 여러 옵션 중에서 무조건 선택할 수 있습니다. 따라서 입력의 일부를 이미 보았을 때 문자열이 끝날 수있는 몇 가지 다른 방법이 있다면 다른 가능성을 처리하는 상태로 전자 전환을 사용하여 표현할 수 있습니다.
예에서 전자 전환은 실제로 매우 유용한 기능을 제공하지 않으며 단순히 사용한 전환 알고리즘의 아티팩트 일뿐입니다. 그 알고리즘은 일반적으로 유용하거나 필요하기 때문에 그것들을 포함합니다. 귀하의 특정 경우에 이것은 사실이 아니므로 그들은 제자리를 찾지 않습니다.