Question

Devise a Turing machine to check the correct nesting of brackets (parentheses). So, your machine should start with a tape with something like (()()(())) on it and halt with T printed on the tape, and it should start with something like (()()(() on the tape and halt with F. That is, correctly nested strings of brackets should give T, and wrongly nested strings of brackets should give the answer F. This example is important since it shows that Turing machines can do more than finite-state machines (they can’t check for bracket balancing of arbitrary depth), and also that they are not only good for arithmetic (binary manipulation) but they can do symbolic computations too.

a) Why can a Turing Machine do the bracket checking but a Finite State Machine cannot?

Answer 1

Why can a Turing Machine do the bracket checking but a Finite State Machine cannot?

A finite-state machine is a restricted Turing machine where the head can only perform "read" operations, and always moves from left to right. Because finite states machines are limited in the sense that they have no memory, a FSM that accepts L can't be constructed. Finite state machines describe a small class of languages where no memory is needed. Turing Machines are the mathematical description of a computer and accept a much larger class of languages than FSMs do. Turing Machines have has more computational power than FSM. There are tasks which no FSM can do, but which Turing Machines can do.

First of all, a (deterministic) finite state machine MM is a 5-tuple (Q,Σ,δ,q0,F)(Q,Σ,δ,q0,F).

QQ is a set of states

ΣΣ is the input alphabet

δδ is the transition function, δ:Q×Σ→Qδ:Q×Σ→Q. This is what tells you what new state you go to when you are in particular state and see a particular symbol.

q0∈Qq0∈Q is the start state.

F⊆QF⊆Q is the set of accepting states.

Now, the basic way this works is you read the input string left to right in one pass. When you see a symbol, you move to a new state based on the transition function. If when you finish reading the string, you’re in an accepting state, you accept the string, otherwise, you reject it. The set of languages that finite state machines accept is the set of regular languages.

A (deterministic) Turing machine M is a 6-tuple (Q,Σ,δ,q0,qaccept,qreject)(Q,Σ,δ,q0,qaccept,qreject) where

QQ is the set of states

ΣΣ is the tape alphabet. This includes the input symbols, symbols you can write on the tape, and the blank symbol.

δ:Q×Σ→Q×Σ×{left,right}δ:Q×Σ→Q×Σ×{left,right} is the transition function. This means that when you’re in a state and see a symbol, you go to another state, write something on the tape, and go to the left or right on the tape.

q0,qaccept,qreject∈Qq0,qaccept,qreject∈Qare the start state, the accepting state and the rejecting state respectively.

The way a Turing machine works is you have an infinitely long tape. When you start the machine, it has its input written on a portion of the tape with trailing blanks. The machine can read a symbol and write a new symbol and go back and forth on the tape as often as it wants. We believe that any computable language can be decided by a Turing machine.