Scribd
Upload
12 views

ToC Test 3 Notes

The document provides a detailed explanation of converting a context-free grammar (CFG) to Chomsky Normal Form (CNF) through various steps including removing ε-productions, unit productions, mixed productions, and long productions. It also introduces the concept of Turing Machines (TM), describing their structure, function, and representation methods, including instantaneous descriptions, transition tables, and diagrams. Additionally, it discusses advanced programming techniques for TMs such as storage in the state, multiple track TMs, and the use of subroutines.

Uploaded by

pranavkeshav4
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

ToC Test 3 Notes

The document provides a detailed explanation of converting a context-free grammar (CFG) to Chomsky Normal Form (CNF) through various steps including removing ε-productions, unit productions, mixed productions, and long productions. It also introduces the concept of Turing Machines (TM), describing their structure, function, and representation methods, including instantaneous descriptions, transition tables, and diagrams. Additionally, it discusses advanced programming techniques for TMs such as storage in the state, multiple track TMs, and the use of subroutines.

Uploaded by

pranavkeshav4
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 30

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

You might also like