Theory of Computation - Lab Manual

S.No
List of Practical
01 Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1} having three consecutive 1's as a substring.
02 Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1} which are divisible by 3.
03 Design a Finite State Machine (FSM) that accepts all decimal string which are divisible by 3.
04 Design a Push Down Automata (PDA) that accepts all string having equal number of 0's and 1's over input symbol {0, 1} for a language 0n1n where n >= 1.
05 Design a Program to create PDA machine that accept the well-formed parenthesis.
06 Design a PDA to accept WCWR where w is any binary string and WR is reverse of that string and C is a special symbol.
07 Design a Turing Machine that calculate 2's complement of given binary string.
08 Design a Turing Machine which will increment the given binary number by 1.
09 Design a Turing Machine that’s accepts the following language anbncn where n>0.
10 Design a Turing Machine to accept WR where w is any binary string and WR is reverse of that string.
Theory of Computation AIM 01 Transition Diagram

Prepared By

Piyush Garg,
Asst. Professor,
Department of CSE,
Corporate Institute of Science & Technology, Bhopal