Theory of Computation (BCS503)
Converting a Grammar to Chomsky Normal Form
Ex 1:
Let G = ( { S, A, B, C, a, c}, {A, B, C}, R, S), where:
R={
S→ aACa
A→ B | a
B→ C | c
C→ cC | ε
}
Step 1: Apply removeEps to eliminate ε - productions.
Compute N, the set of nullable variables. Initially N = {C }.
Because of the rule B→ C, we add B.
Then, because of the rule A→ B, we add A.
So , N= {A, B, C}. Since both A and Care nullable, we derive three new rulesfrom the first
original rule, giving us:
S→ aACa | aAa | aCa | aa
So removeEps returns the rule set:
S→ aACa | aAa | aCa | aa
A→ B | a
B→C|c
C →cC | c
Step 2: Apply removeUnits:
Remove A→ B. Then add A→ C | c.
Remove B → C. Then add B → cC (and B→ c, but it was already there).
Remove A→ C. Then add A→cC (and A→ c, but it was already there).
So removeUnits returns the rule set:
S→ aACa | aAa | aCa | aa
A→ a | c | cC
B → c | cC
C →cC | c
Step 3: Apply removeMixed, which returns the rule set:
S→ Ta AC Ta | Ta A Ta | Ta C Ta | Ta Ta
A→ a | c | Tc C
Dr. HN, Dept. of ISE, RNSIT 1
Theory of Computation (BCS503)
B → c | Tc C
C → Tc C | c
Ta → a
Tc→ c
Step 4: Finally, apply removeLong. which returns the rule set:
S→ Ta S1 S→ Ta S3 S→ Ta S4 S→ Ta Ta
S1 → A S2 S2 → CTa S3 → A Ta S4 → CTa
A→ a | c | Tc C
B → c | Tc C
C → Tc C | c
Ta → a
Tc→ c
Therefore CFG in CNF is G = (V, Σ, R, S), V={S, S1, S2, S3, S4, A, B, C, Ta, Tc, a, c}, Σ = {a,
c}
R={
S→ Ta S1 S→ Ta S3 S→ Ta S4 S→ Ta Ta
S1 → A S2 S2 → CTa S3 → A Ta S4 → CTa
A→ a | c | Tc C
B → c | Tc C
C → Tc C | c
Ta → a
Tc→ c
}
S is the start symbol.
Ex 2:
Dr. HN, Dept. of ISE, RNSIT 2
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 3
Theory of Computation (BCS503)
INTRODUCTION TO PUSH DOWN AUTOMATA
Dr. HN, Dept. of ISE, RNSIT 4
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 5
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 6
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 7
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 8
Theory of Computation (BCS503)
This solution also can be written
Dr. HN, Dept. of ISE, RNSIT 9
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 10
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 11
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 12
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 13
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 14
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 15
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 16
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 17
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 18
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 19
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 20
Theory of Computation (BCS503)
CFG to PDA
Dr. HN, Dept. of ISE, RNSIT 21
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 22
Theory of Computation (BCS503)
Turing Machine(TM)
Turing machine model
The Turing machine can be thought of as finite control connected to a R/W head. It has
one tape which is divided into a number of cells. The block diagram of the basic model for the
Turing machine is given below:
Figure : Turing machine model
• Each cell can store only one symbol.
• The input to and the output from the finite state automaton are affected by the R/W head which
can examine one cell at a time.
• In one move, the machine examines the present symbol under the R/W head on the tape and
the present state of an automaton to determine:
a. a new symbol to be written on the tape in the cell under the R/W head,
b. a motion of the R/W head along the tape: either the head moves one cell left (L), or one
cell right (R).
c. the next state of the automaton, and
d. whether to halt or not.
Dr. HN, Dept. of ISE, RNSIT 23
Theory of Computation (BCS503)
Definition of TM: Turing machine M is a 7-tuple, namely (Q, Σ, 𝚪, 𝛅, q0, B, F), where
1. Q is a finite nonempty set of states.
2. 𝚪 is a finite nonempty set of tape symbols,
3. B ∈ 𝚪 is the blank
4. Σ is a nonempty set of input symbols and is a subset of 𝚪 and B ∉ Σ.
5. 𝛅 is the transition function mapping (q, x) onto (q’, y, D) where D denotes the direction of
movement of R/W head; D = L or R according as the movement is to the left or right.
6. q0 ∈ Q is the initial state, and
7. F ⊆ Q is the set of final states.
Note: The acceptability of a string is decided by the reachability from the initial state to some
final state. So the final states are also called the accepting states. 𝛅 may not be defined for some
elements of Q X 𝚪.
Representation of Turing Machines
We can describe a Turing machine employing
(i) Instantaneous descriptions using move-relations.
(ii) Transition table, and
(iii) Transition diagram (Transition graph).
Ex 1:
Dr. HN, Dept. of ISE, RNSIT 24
Theory of Computation (BCS503)
Ex 2:
Ex 3:
Dr. HN, Dept. of ISE, RNSIT 25
Theory of Computation (BCS503)
Ex 4:
Ex 5:
Ex 6:
Dr. HN, Dept. of ISE, RNSIT 26
Theory of Computation (BCS503)
Ex 7:
Programming Techniques for TM
✓ Storage In The State
• A state is used, whether it is of a FA or PDA or TM, to 'remember' things.
• A state can be used to store a symbol as well. So the state becomes a pair (q, a) where q is
the state (in the usual sense) and a is the tape symbol stored in (q, a). So the new set of
states becomes Q x r.
✓ Multiple Track Turing Machine
In the case of TM defined earlier, a single tape was used. In a multiple track TM. a single
tape is assumed to be divided into several tracks. Now the tape alphabet is required to consist of
k-tuples of tape symbols, k being the number of tracks. Hence the only difference between the
standard TM and the TM with multiple tracks is the set of tape symbols. In the case of the
standard Turing machine, tape symbols are elements of 𝚪; in the case of TM with multiple track,
it is 𝚪k. The moves are defined in a similar way.
FIGURE: Multiple Track Turing Machine
Dr. HN, Dept. of ISE, RNSIT 27
Theory of Computation (BCS503)
✓ Subroutines
We know that subroutines are used in computer languages, when some task has to be
done repeatedly. We can implement this facility for TMs as well.
First a TM program for the subroutine is written. This will have an initial state and a 'return'
state. After reaching the return state, there is a temporary halt. For using a subroutine, new states
are introduced. When there is a need for calling the subroutine, moves are affected to enter the
initial state for the subroutine (when the return state of the subroutine is reached) and to return to
the main program of TM.
Dr. HN, Dept. of ISE, RNSIT 28
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 29
Theory of Computation (BCS503)
Dr. HN, Dept. of ISE, RNSIT 30
