두 개의 테이프 다이어그램 그리기 언어를 결정하는 비 결정적 튜링 기계 M비 결정적 튜링 기계 구성
L = {w∈Σ * | w = U U U ∈Σ *}
내가 어떻게 NDTM을 (언어 적) 구성하는 단계를 설명하고 도움을받을 수 있다면, 내가 그림을 그릴 수 있지만, 내가 대답으로 나올 couldnt는 생각..
는 u*u*u (편집 기록에서 볼), 나는 감히 당신이하려는 것은 u는 어떤 문자열이 알파벳 이상 유 3 (u는 3 회 반복)^형태의 모든 단어의 언어에 의해 당신에게
감사합니다 .
우리의 NDTM은 적어도 한 가지 방법으로 언어의 문자열을 받아 들일 필요가 있으며 언어에없는 것을 받아 들여서는 안됩니다. 특히 핵심은 NDTM을 통과하는 일부 경로가 언어의 모든 문자열을 허용하는 한 NDTM이 해당 언어의 문자열을 거부 할 수 있다는 것입니다.
주어진 첫 번째 단계는 u의 길이를 추측 할 수 있습니다. NDTM은 상태를 q0에서 q1으로 비대칭 적으로 전환 한 다음 오른쪽 스캔 중에 임의의 지점에서 q2으로 3 개의 테이프 기호를 표시 할 수 있습니다 (예 : 밑줄 표시된 기호 버전 작성). 그런 다음 테이프 헤드를 재설정하고 결정 론적 TM을 사용하여 질문에 답할 수 있습니다. 첫 번째 단계에서 추측 한 분할로 인해 u^3이라는 문자열이 생겼습니까?
이것은 부분의 윤곽을 알기 때문에 결정적입니다. 첫 번째 두 부분 (예 : 앞뒤로 튀어 오르게하고 이미 처리 한 기호로 표시)과 두 번째 부분 (동일한 기술을 사용하지만 두 번째 및 세 번째 부분에 적용)을 확인할 수 있습니다.
우리는 문자열이 w|w의 분할을 알고 있는지 여부를 확인하는 문제를 줄였습니다. 이 결정 론적 TM은 생각해내는 것이 더 쉽습니다. 초기 입력을 분리하는 방법을 추측하는 NDTM 이후에 우리는 u^3 형식의 문자열을 허용 할 수있는 NDTM을 얻지 만 가능하지는 않습니다. 이것은 우리가 한 일이고 우리는 끝났습니다.