TOC List of Experiments

Course Name: Theory of Computation

Course Code : AD-501/ Al-601/CS-501 

COs Statements with Blooms Level

CO-1 : Identify the types of automata machines. Blooms Level: L-2

CO-2 : Apply the conversion of NFA to DFA . Blooms Level: L-3

CO-3 : Classify the types of grammars in Chomsky’s hierarchy. Blooms Level: L-2

CO-4: Explain the conversion of PDA to context-free grammar. Blooms Level: L-2

CO-5: Analyze the role of multi-tape Turing machines in computation. Blooms Level: L-4

Exp-1

Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1} having three consecutive 1's as a substring.

Exp-2

Design a Finite State Machine (FSM) that accepts all strings over input symbols {0, 1} which are divisible by 3.

Exp-3

Design a Finite State Machine (FSM) that accepts all decimal strings which are divisible by 3.

Exp-4

Design a Push Down Automata (PDA) that accepts all strings having equal number of 0's and 1's over input symbol {0, 1} for a language 0n1n where n >= 1.

Exp-5

Design a Program to create a PDA machine that accepts the well-formed parenthesis.

Exp-6

Design a PDA to accept WCWR where w is any binary string and WR is the reverse of that string and C is a special symbol.

Exp-7

Design a Turing Machine that calculates 2's complement of a given binary string.

Exp-8

Design a Turing Machine which will increment the given binary number by 1.

Exp-9

Design a Turing Machine that accepts the following language 0n1n2n where n≥1.

Exp-10

Design a Turing Machine to Reverse a String.