Nondeterministic Turing machine:

• An NTM begins working and stops working in the same manner as a DTM.
• Each move of an NTM is nondeterministic. Each Move in an NTM

• reads symbol under its tape head
• According to the transition relation on symbol read from tape and its current state, TM choose 1 move nondeterministically to:

-   write a symbol on the tape

-   move its tape head to the left or right one cell or not

-   changes its state to the next state

Define nondeterministic TM (NTM)

• a quintuple (Q, Σ, Γ, δ, s), where

-   the set of states Q is finite, and does not have halt state h,

-   the input alphabet Σ is a finite set of symbols, not having the blank symbol Δ,

-   the tape alphabet Γ is a finite set of symbols containing Σ, but not having the blank symbol Δ,

-   the initial state s is in Q, and

- the transition fn δ:Q* (∪Γ{Δ}) → 2Q∪{h}*(∪Γ{Δ})*{L,R,S}.

Configuration of an NTM

Definition

• Let T =  (Q, Σ, Γ, δ, s) be an TM.

A configuration of T is an element of Q x Γ* x Γ x Γ*

• Can be stated as

-    (q,l,a,r) or

-    (q,l×a×r) Definition

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Nondeterministic Turing machine in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.