Theory of Computation (CS-501) - B Tech RGPV AICTE Flexible Curricula Notes -->

## COURSE OBJECTIVE

 To understand computability, decidability, and complexity through problem solving.
 To analyse and design abstract model of computation & formal languages
 To understand and conduct mathematical proofs for computation and algorithms.

## Syllabus

UNIT 1:
Introduction of Automata Theory: Examples of automata machines, Finite Automata as a language acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy to Moore and vice versa.

UNIT 2:
Types of Finite Automata: Non Deterministic Finite Automata (NDFA), Deterministic finite automata machines, conversion of NDFA to DFA, minimization of automata machines, regular expression, Arden’s theorem. Meaning of union, intersection, concatenation and closure, 2 way DFA.

UNIT 3:
Grammars: Types of grammar, context sensitive grammar, and context free grammar, regular grammar. Derivation trees, ambiguity in grammar, simplification of context free grammar, conversion of grammar to automata machine and vice versa, Chomsky hierarchy of grammar, killing null and unit productions. Chomsky normal form and Greibach normal form.

UNIT 4:
Push down Automata: example of PDA, deterministic and non-deterministic PDA, conversion of PDA into context free grammar and vice versa, CFG equivalent to PDA, Petrinet model.

UNIT 5:
Turing Machine: Techniques for construction. Universal Turing machine Multitape, multihead and multidimensional Turing machine, N-P complete problems. Decidability and Recursively Enumerable Languages, decidability, decidable languages, undecidable languages, Halting problem of Turing machine & the post correspondence problem.

• Unit 1
• Unit 2
• Unit 3
• Unit 4
• Unit 5

## RECOMMENDED BOOKS

 Introduction to Automata Theory Language & Computation, Hopcroft& Ullman, Narosa Publication.
 Element of the Theory Computation, Lewis &Christors, Pearson.
 Theory of Computation, Chandrasekhar & Mishra, PHI.
 Theory of Computation, Wood, Harper & Row.
 Introduction to Computing Theory, Daniel I-A Cohen, Wiley.

## COURSE OUTCOMES

After completion of this course, the students would be able to:
CO1.explain the basic concepts of switching and finite automata theory & languages.
CO2.relate practical problems to languages, automata, computability and complexity.
CO3.construct abstract models of computing and check their power to recognize the languages.
CO4.analyse the grammar, its types, simplification and normal form.
CO5.interpret rigorously formal mathematical methods to prove properties of languages, grammars and automata.
CO6.develop an overview of how automata theory, languages and computation are applicable in engineering application.

## LIST OF EXPERIMENTS

1. Design a Program for creating machine that accepts three consecutive one.
2. Design a Program for creating machine that accepts the string always ending with 101.
3. Design a Program for Mode 3 Machine
4. Design a program for accepting decimal number divisible by 2.
5. Design a program for creating a machine which accepts string having equal no. of 1’s and 0’s.
6. Design a program for creating a machine which count number of 1’s and 0’s in a given string.
7. Design a Program to find 2’s complement of a given binary number.
8. Design a Program which will increment the given binary number by 1.
9. Design a Program to convert NDFA to DFA.
10. Design a Program to create PDA machine that accept the well-formed parenthesis.
11. Design a PDA to accept WCWR where w is any string and WR
is reverse of that string and C is a Special symbol. 12. Design a Turing machine that’s accepts the following language a n b n c n where n>0.

## COURSE OUTCOMES

After completion of this course, the students would be able to:
CO1: judge various computational models.
CO2: construct abstract models of computing.
CO3: justify the power of abstract models in computing to recognize the languages.
CO4: demonstrate analytical thinking and intuition for problem solving in the related areas.
CO5: discuss the limitations of computation in problem solving.
CO6: follow set of rules for syntax verification.

## You May Also Like

#### Services

###### COMPLETELY FREE !!!

Yup, everything is free....

###### NO REGISTRATION REQUIRED

User doesn't have to register for accessing the files, all the files are free & universally accessible without any condition or restriction.

###### RESPONSIVE DESIGN & USER-FRIENDLY

Our webpages are responsive & user-friendly, which means it will automatically adjust according to your device screen size and you will find stuff without ant hustle.

All the files are uploaded on our super-fast servers so that they can be easily downloaded with high speed.

###### NEW PROJECTS

For providing a better experience to our users we are developing our Android application, the application will have a lot of awesome features so stay tuned ;).

###### AWESOME SUPPORT TEAM

Our AI-powered Chatbots are always here to help you so, feel free to ask any question or report if you face any problem. Our team also monitors all chatbots traffic & they will contact you if chatbot fails to help.