CS8501 Theory of Computation Previous Year Question Paper Download

CS8501 Theory of Computation Previous Year Question Paper Download


OBJECTIVES:

· To understand the language hierarchy

· To construct automata for any given pattern and find its equivalent regular expressions

· To design a context free grammar for any given language

· To understand Turing machines and their capability

· To understand undecidable problems and NP class problems

UNIT I   AUTOMATA FUNDAMENTALS                                                                               

Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions

UNIT II   REGULAR EXPRESSIONS AND LANGUAGES                                                    

Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties of Regular Languages – Equivalence and Minimization of Automata.

UNIT III  CONTEXT FREE GRAMMAR AND LANGUAGES                                               

CFG – Parse Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown Automata – Languages of a Pushdown Automata – Equivalence of Pushdown Automata and CFG, Deterministic Pushdown Automata.

UNIT IV  PROPERTIES OF CONTEXT FREE LANGUAGES                                                

Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines

-Programming Techniques for

UNIT V  UNDECIDABILITY                                                                                                       

Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP.



CS8501 Theory of Computation Previous Year Question Paper for Regulation 2017 question paper Download

  • CS8501 Theory of Computation Apr/May 2019 Question Paper
  • CS8501 Theory of Computation Nov/Dec 2019 Question Paper


Related Downloads


Related Post

MA8551 Algebra and Number Theory Previous Year Question Paper Download

CS8591 Computer Networks Previous Year Question Paper Download

EC8691 Microprocessors and Micro controllers Previous Year Question Paper

CS8592 Object Oriented Analysis and Design Previous Year Question Paper Download

1
Leave a Reply

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Daniel Stewart R Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Daniel Stewart R
Guest
Daniel Stewart R

The link is Not working