CIS 2620 Exam 2

The Tape of a TM:

• Sequence (or array) of cells

• Each cell holds a symbol (an element of “tape alphabet” G)

• Potentially unbounded on the right

• Plays the role of memory of a modern computer

• Initially, the tape holds the input string, with blanks _ to the right

Like a DFA, a TM has ______________ many states Q, one of which is initial q0

finitely

_____________ of a TM points to a tape cell (analogous to an array index)

“Head”

Single transition (or one execution step) of TM:

• Based on current state and symbol read by head, overwrite current symbol, move left/right, and update state

• Machine can go back and forth on tape reading/writing tape cells

What is the algorithm for designing a Turing machine for palindromes?

High-level algorithm:

If first symbol is a, then move all the way to right to check that last symbol equals a (and similar check if first symbol is b).

If the check fails, reject the input

If the check succeeds, move back to the left, and repeat

A TM M consists of:

• A finite set Q of states

• Initial state q0 (belongs to Q)

• Accepting state qa (belongs to Q)

• Rejecting state qr (belongs to Q and different from qa)

• Tape alphabet Γ

• Input alphabet Σ (a subset of Γ)

• Blank symbol _ (belongs to Γ but not in Σ) Transition function δ : Q x Γ → Q x Γ x {L, R}

  • δ(q, σ) = (q’, g, L/R) means that in state q, if current tape cell contains σ, then write γ, move left/right, and goto state q’

As a TM M executes on its input w, what all can happen?

1. State becomes accepting state : M accepts input w

2. State becomes rejecting state : M rejects input w

3. From left-most cell, M wants to move left : M rejects w

   1. M goes into an infinite loop

The configuration of any machine is …

All information needed to determine future behavior

TM Configuration = ???

State + Contents of tape + Position of read h