저는 NDTM을 처음 접했지만 튜링 기계의 개념을 이해합니다. 그것이 내가 약간 혼란스러워 NDTM에 올 때, 나는 언어에 대한 NDTM을 개발하기로되어 있어요 {A, B, C}와비 결정적 튜링 기계
L = {w ∈ Σ*| Ǝv ∈ Σ*, Ǝn >= 2 with w = v (to the power of) n }
우선 예를 들어, L을 읽는 방법입니다 meaning의 의미는 무엇입니까? NDTM은 하나의 결과에 대해 예를 들어 다음과 같은 두 가지 가능성을 제공한다는 것을 이해합니다. 우리가 가지고있는 것과없는 것, 내가 올바른지 누군가에게 나를 도울 수 있습니까?
"숙제"라고 표시해야합니다.
Ǝ는
∈는 우리가 가지고, 우리가 읽을 수있는 지금
"의 요소"이 경우에
Σ는 "언어 기호 세트"입니다 ({a, b,c})를 "존재"입니다 이 언어. 그래서 L 단어 단어 v이 존재하고 w이 vn 번 반복하는 n >= 2 있도록이 존재하도록 {a, b, c}*에서 w의 집합입니다. 예 : ababab = (ab)^3 ∈ L.
지금이 언어를 표현하기 위해, 튜링 기계, M을 마련하려는, 그래서 당신이 고려해야 할 :
M이 어떻게 종료되는지 보장 할 수 있습니다.우리는 a이 아닌 것을 알 수 있습니다 Lv^n의 길이 (아웃 라이어이다하지만 빈 문자열의 경우 0) 이상 2 인 것을 의미하는 n >= 2 때문이다. 마찬가지로 b 및 c에 대해서도 마찬가지입니다. 그러한 고려와 지식이 n >= 2 인 경우 어떤 단어가 허용되지 않는지 파악하십시오 (예 : b, abc, cab, cca 등으로 생각하십시오).
이 같은 문제의 올바른 NDTM입니다. –
정말 그렇습니까? 그 진술은 수학에서 [set-builder notation] (http://www.mathsisfun.com/sets/set-builder-notation.html)입니다. 기본적으로 L은 시그마에있는 w의 집합입니다. 시그마에 v가있는 경우 w = v^n, 여기서 n> = 2입니다. 적어도 하나의 질문에 대답하기 위해, 거꾸로 붙어있는 E는 기본적으로 "there exists"또는 "there is one"을 읽습니다. –
@ 2-BitAlchemist는 w가 2의 배수 인 길이를 가져야 만하는 것과 같지 않습니까? 잘 나는 여기에서 당신이 컴퓨터 주제에 관해 어떤 종류의 질문이라도 물을 수있다!! –
@ S.N StackOverflow는 특정 프로그래밍 관련 질문 만위한 것입니다. – admdrew