비 결정적 유한 자동화 문제

Im 약간의 공부를하고 있는데,이 작은 비 결정적 알고리즘을 처리 할 때 약간 혼란 스럽습니다. 0 또는 1이 다시 리디렉션 될 것이므로 q1을 사용하여 브랜드로 분리된다는 것을 이해합니다. q2로 나가는 화살표는 1이지만 왜 q3으로 나뉘겠습니까? 나는 메신저 (0, 빈 문자열)를 잘못 읽은 것처럼 느낍니다. 어떤 설명도 훌륭합니다.비 결정적 유한 자동화 문제

enter image description here

출처

2011-09-19 jfisk

enter image description here 빈 문자열

는 에서 어떤 시간이 걸릴 수 있다는 것을 의미한다. 이 경우 1은 q2로, q2는 q3에 빈 문자열 화살표가 있기 때문에 1을 취합니다. 또한 입력의 다음 비트를 얻지 않고 즉시이를 수행합니다.

출처

2011-09-19 03:56:01 quasiverse

아 좋아요. 그렇다면 4 분기 1 분기가 q2에서 왜 죽을까요? – jfisk

... 입력 '1'에 대해 q2를 떠나는 화살표가 없기 때문에 분기가 죽는다 – Nemo

q1에서 시작하여 입력 1을 얻습니다. q1, q2 또는 q3으로 이동 한 후 다음 입력을 얻을 수 있습니다 . 이 경우 q2로 가면 다음 입력을 가져 와서 q3으로 가면 q3으로 곧바로 들어가서 입력을 얻는 것과 같습니다. 기본적으로 옆에있는 q3 경로의 복제본이므로 표시하지 않습니다. – quasiverse

답변

관련 문제