ANDHRA UNIVERSITY, WALTAIR

 

M.Sc. APPLIED MATHEMATICS, FOURTH SEMSTER

 

AM-403 :  THEORETICAL COMPUTER SCIENCE

 

[ A total of seven questions are to be set.  All questions carry equal marks.  The first question which is compulsory carries 20 marks.  It consists of  4 short answer sub questions each of five marks covering the entire syllabus.  The remaining six questions each carrying 20 marks are to be set as suggested in the body of the syllabi.]

---

The Theory of Automata: Definition of an Automata, Description of a Finite Automation, Transition systems, properties of transition functions, acceptability of a string  by a finite automaton, Non Deterministic finite state machines, the equivalences of DFA and NDFA, Melay and Moore models, Minimisation of finite automata.

Formal languages: basic definitions and examples, Chomskty classification of Languages, Languages and their relation, Recursive and recursively enumerable sets, operations of languages, languages and automata. 

[Three questions are to be set]

Regular sets and regular grammars: Regular expressions, finite automata and regular expressions, pumping lemma for regular sets, application of pumping lemma, closure properties of regular sets, regular sets and regular grammars.

Context –free Languages: Context- free languages and derivation trees, ambiguity in context-free Grammars, simplification of context-free grammars, normal forms for context-free grammars.

Turing Machines and Linear Bounded Automata: Turing Machine model, Representation of Turing Machines, Language acceptability by Turing Machines, Design of Turing Machines, Universal Turing Machines and other modifications.

[Three questions are to be set]

 ________________________________________________________________________________________________________

 Scope and treatment of the book :

Theory of Computer science ( Automata, Languages and computation) Chapters : 2,3,4,5.1 to 5.4 and 7.1 to 7.5  by K.L.P.Mishra, N.Chandrasekaran, PHI , Second edition, 1998.