TURING MACHINES
Empty Production Removal
The productions of context-free grammars can be coerced into a variety of forms without affecting the expressive power of the grammars. If the empty string does not belong to a language, then there is a way to eliminate the productions of the form A → λ from the grammar. If the empty string belongs to a language, then we can eliminate λ from all productions save for the single production S → λ. In this case we can also eliminate any occurrences of S from the right-hand side of productions.
Procedure to find CFG with out empty Productions
Unit production removal
Left Recursion Removal
NORMAL FORMS
Two kinds of normal forms viz., Chomsky Normal
Form and Greibach Normal Form (GNF) are
Chomsky Normal Form (CNF)
Any context-free language L without any λ-
production is generated by a grammar is which productions are of the form A →
BC or A→ a, where A, B ∈VN , and a
∈ V
Τ. Procedure to find Equivalent Grammar in CNF
(i) Eliminate
the unit productions, and λ-productions if any,
(ii) Eliminate
the terminals on the right hand side of length two or more.
(iii) Restrict
the number of variables on the right hand side of productions to two. Proof:
For Step (i): Apply the
following theorem: “Every context free language can be generated by a grammar
with no useless symbols and no unit productions”.
At the end of this step the RHS of any
production has a single terminal or two or more symbols. Let us assume the
equivalent resulting grammar as G = (VN ,VT ,P ,S ).
For Step (ii): Consider any production of the
form
Pumping Lemma for CFG
A “Pumping Lemma” is a theorem used to show
that, if certain strings belong to a language, then certain other strings must
also belong to the language. Let us discuss a Pumping Lemma for CFL. We will
show that , if L is a context-free language, then strings of L that are at
least ‘m’ symbols long can be “pumped” to produce additional strings in L. The
value of ‘m’ depends on the particular language. Let L be an infinite context-free
language. Then there is some positive integer ‘m’ such that, if S is a string
of L of Length at least ‘m’, then
(i) S
= uvwxy (for some u, v, w, x, y)
(ii) |
vwx| ≤ m
(iii) |
vx| ≥ 1
(iv) uv iwx
i y∈L.
for all non-negative values of i.
It should be understood that
(i) If
S is sufficiently long string, then there are two substrings, v and x,
somewhere in S. There is stuff (u) before v, stuff (w) between v and x, and
stuff (y), after x.
(ii) The
stuff between v and x won’t be too long, because | vwx | can’t be larger than
m.
(iii) Substrings
v and x won’t both be empty, though either one could be.
(iv) If
we duplicate substring v, some number (i) of times, and duplicate x the same
number of times, the resultant string will also be in L.
Definitions
A variable is useful if it occurs in the
derivation of some string. This requires that
(a) the variable occurs in some sentential form
(you can get to the variable if you start from S), and (b) a string of
terminals can be derived from the sentential form (the variable is not a “dead
end”). A variable is “recursive” if it can generate a string containing itself.
For example, variable A is recursive if
Proof of Pumping Lemma
(a) Suppose we have a CFL given by L. Then there
is some context-free Grammar G that generates
L. Suppose
(i) L
is infinite, hence there is no proper upper bound on the length of strings
belonging to L.
(ii) L
does not contain l.
There are only a finite number of variables in a
grammar and the productions for each variable have finite lengths. The only way
that a grammar can generate arbitrarily long strings is if one or more
variables is both useful and recursive. Suppose no variable is recursive. Since
the start symbol is non recursive, it must be defined only in terms of
terminals and other variables. Then since those variables are non recursive,
they have to be defined in terms of terminals and still other variables and so
on.
After a while we run out of “other variables”
while the generated string is still finite. Therefore there is an upper bond on
the length of the string which can be generated from the start symbol. This
contradicts our statement that the language is finite.
Hence, our assumption that no variable is
recursive must be incorrect.
(b) Let us consider a string X belonging to L.
If X is sufficiently long, then the derivation of X must have involved
recursive use of some variable A. Since A was used in the derivation, the
derivation should have started as
Usage of Pumping Lemma
Hence our original assumption, that L is context
free should be false. Hence the language L is not context-free.
Example
Check whether the language given by L = {a mbmcn
: m ≤ n ≤ 2m} is a CFL or not.
Solution
Turing machine:
Informal Definition:
We consider here a basic model of TM which is
deterministic and have one-tape. There are many variations, all
The basic model of TM has a finite set of states,
a semi-infinite tape that has a leftmost cell but is infinite to the right and
a tape head that can move left and right over the tape, reading and writing
symbols.
For any input w with |w|=n, initially it is
written on the n leftmost (continguous) tape cells. The infinitely many cells
to the right of the input all contain a blank symbol, B whcih is a special tape
symbol that is not an input symbol. The machine starts in its start state with
its head scanning the leftmost symbol of the input w.
Depending upon the symbol scanned by the tape
head and the current state the machine makes a move which consists of the
following:
• writes
a new symbol on that tape cell,
• moves
its head one cell either to the left or to the right and
• (possibly)
enters a new state.
The action it takes in each step is determined
by a transition functions. The machine continues computing (i.e.
• it decides to "accept" its input by entering a special state called accept or final state or On some inputs the TM many keep on computing forever without ever accepting or rejecting the input, in which case it is said to "loop" on that input
Formal Definition :
So, given the current state and tape symbol being read, the transition function describes the next state, symbol to be written on the tape, and the direction in which to move the tape head.
Transition function :
1. replaces
the symbol X by Y on the tape
2. goes
to state p, and
3. the
tape head moves one cell ( i.e. one tape symbol ) to the left ( or right ) if D
is L ( or R ).
The ID (instantaneous description) of a TM
capture what is going out at any moment i.e. it contains all the information to
exactly capture the "current state of the computations".
It contains the following:
• The
current state, q
• The
position of the tape head,
• The
constants of the tape up to the rightmost nonblank symbol or the symbol to the
left of the head, whichever is rightmost.
Note that, although there is no limit on how far
right the head may move and write nonblank symbols on the tape, at any finite
time, the TM has visited only a finite prefix of the infinite
Moves
of Turing Machines
Special
Boundary Cases
• The representation of IDk contains an accepting state.
The set of strings that M accepts is the language of M, denoted L(M), as defined
More about configuration and acceptance
The Halting Problem
The input
to a Turing machine is a string. Turing machines themselves can be written as
strings. Since these strings can be used as input to other Turing machines. A
“Universal Turing machine” is one whose input consists of a description M of some arbitrary Turing machine, and
some input w to which machine M is to
be applied, we write this combined input as M
+ w. This produces the same output
that would be produced by M. This is written as
Universal
Turing Machine (M + w) = M
(w).
As a
Turing machine can be represented as a string, it is fully possible to supply a
Turing
machine
as input to itself, for example M (M). This is not even a particularly
bizarre thing to do for example, suppose you have written a C pretty printer in
C, then used the Pretty printer on itself. Another common usage is
Bootstrapping—where some convenient languages used to write a minimal compiler
for some new language L, then used this minimal compiler for L to write a new,
improved compiler for language L. Each time a new feature is added to language
L, you can recompile and use this new feature in the next version of the
compiler. Turing machines sometimes halt, and sometimes they enter an infinite
loop.
A Turing
machine might halt for one input string, but go into an infinite loop when
given some other string. The halting problem asks: “It is possible to tell, in
general, whether a given
machine
will halt for some given input?” If it is possible, then there is an effective
procedure to look at a Turing machine and its input and determine whether the
machine will halt with that input. If there is an effective procedure, then we
can build a Turing machine to implement it. Suppose we have a Turing machine
“WillHalt” which, given an input string M
+ w, will halt and accept the string
if Turing machine M halts on input w and will halt and reject the string if
Turing machine M does not halt on
input w. When viewed as a Boolean
function, “WillHalt (M, w)” halts and returns “TRUE” in the
first case, and (halts and) returns “FALSE” in the second.
Theorem
Turing
Machine “WillHalt (M, w)” does not exist.
Proof: This theorem is proved by
contradiction. Suppose we could build a machine “WillHalt”. Then we can certainly build a second machine, “LoopIfHalts”, that
will go into an infinite loop if and only if “WillHalt” accepts its input:
Function LoopIfHalts (M, w):
if WillHalt (M, w) then while true do
{ }
else
return false;
We will
also define a machine “LoopIfHaltOnItSelf” that, for any given input M, representing a Turing machine, will
determine what will happen if M is
applied to itself, and loops if M
will halt in this case.
Function LoopIfHaltsOnItself (M): return LoopIfHalts (M, M):
Finally,
we ask what happens if we try:
Func tion Impos sible:
return LoopIfHaltsOnItself
(LoopIfHaltsOnItself):
This
machine, when applied to itself, goes into an infinite loop if and only if it
halts when applied to itself. This is impossible. Hence the theorem is proved.
Programming
The Theorem of “Halting Problem” does not say that we can never determine whether or not a given program halts on a given input. Most of the times, for practical reasons, we could eliminate infinite loops from programs. Sometimes a “meta-program” is used to check another program for potential infinite loops, and get this meta-program to work most of the time.
The
theorem says that we cannot ever write such a meta -program and have it work
all of the time. This result is also used to demonstrate that certain other
programs are also impossible. The basic outline is as follows:
(i) If we
could solve a problem X, we could
solve the Halting problem
(ii) We cannot
solve the Halting Problem
A Turing
machine can be "programmed," in much the same manner as a computer is
programmed.
When one specifies the function which we usually call δ for a Tm, he is really writing a
program for the Tm.
1. Storage in finite Control
The
finite control can be used to hold a finite amount of information. To do so,
the state is written as a pair of elements, one exercising control and the
other storing a symbol. It should be emphasized that this arrangement is for
conceptual purposes only. No modification in the definition
of the
Turing machine has been made.
Example
Consider
the Turing machine
2. Multiple Tracks
We can
imagine that the tape of the Turing machine is divided into k tracks, for any
finite k. This arrangement is shown in Fig., with k = 3. What is actually done
is that the symbols on the tape are considered as k-tuples. One component for
each track.
Example
The tape
in Fig. can be imagined to be that of a Turing machine which takes a binary
input
greater
than 2, written on the first track, and determines if it is a prime. The input
is surrounded by ¢ and $ on the first track.
Thus, the
allowable input symbols are [¢, B, B], [0, B, B ], [1, B, B ], and [$, B, B].
These
symbols
can be identified with ¢, 0, 1, and $, respectively, when viewed as input
symbols. The symbol can be represented by [B, B, B ]
To test
if its input is a prime, the Tm first writes the number two in binary on the
second track and copies the first track onto the third track. Then, the second
track is subtracted, as many times as possible, from the third track,
effectively dividing the third track by the second and leaving the remainder. If
the remainder is zero, the number on the first track is not a prime. If the
remainder is nonzero, increase the number on the second track by one.
If now
the second track equals the first, the number on the first track is a prime,
because it cannot be divided by any number between one and itself. If the
second is less than the first, the whole operation is repeated for the new
number on the second track. In Fig., the Tm is testing to determine if 47 is a
prime. The Tm is dividing by 5; already 5 has been subtracted twice, so 37
appears on the third track.
3. Subroutines
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.