6
DFA의 다이어그램을 어떻게 튜링 머신으로 변환 할 수 있습니까? DFA에서 허용하는 언어를 찾아 튜링 머신을 만들어야합니까? 아니면 직접적인 방법이 있습니까?DFA를 튜링 기계로 변환하는 방법은 무엇입니까?
감사합니다.
A
답변
8
DFA의 각 전환은 입력 문자를 읽고 전환을 따라 한 다음 입력의 다음 문자로 이동합니다. 모든 입력이 읽히면 DFA는 수락 상태에 있으면 수락하고 그렇지 않으면 거부합니다.
튜링 기계로 직접 시뮬레이션 할 수 있습니다. DFA의 각 상태에 대해 하나의 상태를 만들어 Turing 머신의 유한 상태 컨트롤을 구축하십시오. 문자 C에서 DFA의 각 전환에 대해 TM에서 해당 전환을 문자 C를 읽을 때 어떤 임의의 문자를 테이프에 다시 써 넣습니다 (어떤 것이 든 상관 없습니다). 그런 다음 테이프 헤드를 오른쪽으로 이동합니다 (테이프의 다음 지점으로). 그런 다음 각 상태에 대해 해당 상태에서 TM의 승인 상태 또는 TM의 거부 상태 (해당 상태가 수락 또는 거부 중임)를 기준으로 빈 기호에 대한 전환을 도입하십시오. 이 TM은 입력 문자열을 수동으로 단계별로 실행하고 실행이 끝날 때 최종적으로 수락할지 거부 할지를 결정하여 DFA를 효과적으로 실행합니다.
희망이 도움이됩니다.
상태가 바뀌지 않는 문자 c가 읽힐 때 어떤 일이 발생합니까? 임의의 문자가 쓰여지고 테이프 헤드가 여전히 움직입니까? – Paradox
@ 패러독스 DFA의 대부분 정의에서 DFA는 각 문자 및 각 상태에 대해 정의 된 전환을 가져야합니다. 마찬가지로 대부분의 TM은 입력으로 입력 할 수있는 기호의 종류를 제한 할 수있는 방식으로 정의되어 있으므로이 점에 대해 걱정할 필요가 없습니다. 발생할 수있는 TM 기호는 DFA가 전환이 정의되었습니다. 또는 DFA의 언어가 알파벳의 문자 만 사용하도록 제한되어 있기 때문에 외국 문자가 보이면 문자열이 해당 언어로되어 있지 않다는 것을 알 수 있습니다. – templatetypedef