Theory of Computation Syllabus

MS-11 Theory of Computation
                                                  Unit – I
Formal Languages, Need for formal computational models, Non-computability and examples of non-
computable problems, diagonal argument and Russel's paradox, Chomsky hierarchy of formal languages,
Regular languages, Regular sets, regular grammars, computable and non-computable problems.
                                                  Unit – II
Deterministic and Non-Deterministic finite automata, equivalence of deterministic and non-deterministic
finite automata, Kleen's characterization theory for sets accepted by finite automata, finite state machines and
their relations to combinatorial switching circuits, complexity, State equivalence and state minimization of
finite automata, pumping lemma, Algebra decomposition and structure theory.
                                                   Unit – III
Context Free Grammers, Chomsky & Greibiech normal form theorems, Self embedding, Equivalence of
context free languages and sets accepted by non-deterministic push down store automata, pushdown
automata, closure properties of context free languages, Ambiguity, Ambiguous grammars, Parsing: Early's,
Cook-Kasami-Young, Tomito's, top-down and bottom-up methods, Restrictions of push-down automata.
                                                 Unit – IV
Linear bounded automata (LBA): Power of LBA, closure properties
Turing machine (TM): one-tape, Multitape Turing machines and related formalism for recognition, Time and
space complexity in terms of TM, Construction of TM for various problems, Unsolvability of the halting
problem, reduction of post correspondence problem to the halting problem, Undecidable properties of
grammars. Recursive and recursively enumerable language.

Text Books
1 Kamla kirtheivshan & Rama R, Automata theory & Computation, PEARSON, 1/e
2 Peter Linz, An introduction to formal language & automata, Jones & Bartlete pub. 5/e

Reference Books:
1. Hopcroft,J.E.&Ullman,J.D. Formal languages and their relation to Automata, Addison-Wasley
2. E.V.Krishnamurthy, Introductory Theory of Computer Science Ease-West press Pvt. Ltd.
3. Salomma, A.K. Formal languages, Academic press.
4. Lewis, H.R.& Papadimitrious, C.H. Elements of the Theory of Computation.PHI.
5. Zoha Mauna, Mathematical Theory of Computation, Wiley Inter-science.

COMPILER CONSTRUCTION SYLLABUS

MCA-504 SYSTEM PROGRAMMING AND COMPILER CONSTRUCTION

UNIT – I

System Software: Definition, evolution of System Software. Assemblers: Elements of Assembly language programming, overview of assembly process, design options- one pass assembler & multi pass assembler. Macro processors: Basic functions, Design options-Recursive macro expansion, General purpose macro processors, Macro processing within language translators. Loaders & Linkage Editors: Loading, Linking & Relocation, Program relocatibility, Overview of Linkage editing, linking for program overlays.

UNIT – II

Compilers: Phases and passes, analysis-synthesis model of translation, compiler construction tools. Lexical Analysis: Process of lexical analysis, finite state automata, DFA and NFA, recognition of regular expressions, LEX. Formal  grammars and their application to syntax analysis, BNF notation, ambiguity, YACC. The syntactic specification of programming languages: Context free grammars, derivation and parse trees, capabilities of CFG.

UNIT – III

Parsing Techniques: top down & bottom-up parsing, Shift reduce parsing, operator precedence parsing, predictive parsers Automatic Construction of efficient Parsers: LR parsers, the canonical Collection of LR(0) items, constructing SLR parsing tables, constructing Canonical LR parsing tables, Constructing LALR parsing tables, using ambiguous grammars, an automatic parser generator, implementation of LR parsing tables, constructing LALR sets of items.

UNIT – IV

Intermediate Code Generation: Issues in the design of a code generator, Intermediate languages, generating intermediate code for declarative statement, assignment statement, Boolean expression, and case statement. Code  Optimization: potential cases of code optimization, optimization of basic blocks, loops in flow graphs, code improving transformation. 

Text books:

1. Alfred V Aho and Jeffery D Ullman, Principles of Compiler Design,

Narosa/Addison Wesley.

2. Dhamdhere D.M, System programming and operating system,

(Tata Mc-Graw-Hill).

3. Beck L. Leland, System Software, 3/e, Addison Wesley - 2000.

Reference Books:

1. Aho, Sethi, & Ullman, Compilers Principles, Techniques and Tools, Addison

Wesley.

2. Jean Paul Tremblay and Sorenson, The Theory and Practice of Compiler

Writing, McGraw Hill.

3. Donovan J. John, System Programming, Tata McGraw Hill.