|
Theory of Automata and Computation |
|
ETCS 202 – THEORY OF AUTOMATA AND COMPUTATION L T P 3 1 4 SYLLABUS Deterministic and Nondeterministic Computation, Equivalence of Deterministic and Nondeterministic Automata, Regular Expression, Regular Languages, Regular Grammars, Closure Property of Regular Languages, Context Free Grammars, Pushdown Automata. Context-Free and Non-Context Free Languages, Turing Machines, Church-Turing Thesis, Nondeterministic and Universal Turing Machines, Variations of Standard Turing Machines, Recursively Enumerable and Recursive Languages, Unrestricted Grammars, Chomsky Hierarchy, Turing Machine Halting Problem, Undecidable Problem for Recursively Enumerable Languages, Post Correspondence Problem. Post Systems, Matrix Grammars, Markov Algorithms, Growth Rates of Functions, Turing Machines and Complexity Classes, P and NP Completeness, Cook's Theorem. Art of Designing Sequential Circuits, Synchronous and Asynchronous Sequential Circuits (Pulse Mode and Fundamental Mode), Mealy and Moore Models of Sequential Machines, Obtaining Flow Table Form Description and Minimization of Flow table for Completely Specified Machines. Introduction to Incompletely Specified Machine and Minimization of Flow table for same, State Assignments Problems in Sequential Machines and Serial and Parallel Decompositions of Machines. * * * * * LECTURE PLAN Lectures Topics 1 - 3 Deterministic and Nondeterministic Computation 4 & 5 Equivalence of Deterministic and Nondeterministic Automata 6 - 9 Regular Expression, Regular Languages, Regular Grammars 10 - 12 Closure Property of Regular Languages 13 - 15 Context Free Grammars 16 - 18 Pushdown Automata 19 - 21 Context-Free and Non-Context Free Languages 22 - 24 Turing Machines, Church-Turing Thesis 25 - 27 Variations of Standard Turing Machines, Nondeterministic and Universal Turing Machines 28 - 30 Recursively Enumerable and Recursive Languages, Unrestricted Grammars, Chomsky Hierarchy 31 - 33 Turing Machine Halting Problem, Undecidable Problem for Recursively Enumerable Languages, Post Correspondence Problem 34 - 36 Post Systems, Matrix Grammars, Markov Algorithms 37 - 39 Growth Rates of Functions, Turing Machines and Complexity Classes, P and NP Completeness, Cook's Theorem 40 & 41 Art of Designing Sequential Circuits, Synchronous and Asynchronous Sequential Circuits (Pulse Mode and Fundamental Mode) 42 Mealy and Moore Models of Sequential Machines 43 Obtaining Flow Table Form Description and Minimization of Flow table for Completely Specified Machines 44 & 45 Introduction to Incompletely Specified Machine and Minimization of Flow table for same, State Assignments Problems in Sequential Machines and Serial and Parallel Decompositions of Machines * * * * * REFERENCE BOOKS 1. Introduction to Automata Theory, Languages, and Computation - John E. Hopcroft, Jeffery D. Ullman (Narosa Publishing House) 2. An Introduction to Formal Languages and Automata - Peter Linz (Narosa Publishing House) * * * * * ASSIGNMENTS ASSIGNMENT NO. 1 Q1. Find DFA’s that recognizes the following sets: a. L = {x belongs to {a, b, c} * / |x| is a multiple of 2 or 3} b. L = {x belongs to {a, b, c} * / abc is a substring of x} c. L = {x belongs to {a, b} * / (!x!a as odd) ^ (!x!b is even)} d. L = {x belongs to {a, b} * / (!x!a as even) V (!x!b is odd)} e. L = {x belongs to {a, b} * / |x|a as odd} Q2. Construct NFA that accepts the languages: a. L = {x belongs to {a, b, c} * /x contains exactly one to immediately following C} b. L = {x belongs to {0, 1} * / every block of five consecutive symbols in x contains at least two 0’s} c. L = {x belongs to {0, 1} * /x is starting with 1 and |x| divisible by 3} d. L = {x belongs to {a, b} * /x contains any number of a’s followed by at least a single b} e. The set of all strings over {0, 1} having at most one pair of 0’s or at most one pair of 1’s. Q3. Construct DFA from NFA’s given in question (2). Q4. Construct DFA equivalent to the following regular expression: i. i0 + (0 + 11) 0 * 1 ii. 01 [(10 * + 111)* + 0]* 1 iii. (aab*ab)* Q5. Show that the following languages are not finite state languages: a. L = {ai bj / i < j} b. L = {an / n is prime} c. L = {ok / k = 2i, i > 1} * } d. L = {WWR / W belongs to {a, b} * } Q6. Construct regular grammars for the following languages on {a, b} i. L = {an bm / n > 2, m > 3} ii. L = {W belongs to {a, b} * / na(w) and nb(w) in both even } * * * * * ASSIGNMENT NO. 2 Q1. Find context free grammars for the following (with n > 0, m > 0) i. L = {an bm / n > m} ii. L = {an bm ck /n = m or m < k} iii. L = {an bm ck / K = n + m} Q2. Show that the following grammars are ambiguous: i. S --> AB/aaB, A --> a/Aa, B --> b ii. S --> aSbS / bSaS / ? Q3. Eliminate useless symbols and productions from the following grammars: i. S --> aS/A/c, A --> a, B --> aa, C --> acb ii. S --> a/aA/B/C, A --> aB?, B --> Aa, C --> cCD, D --> ddd Q4. Convert the following grammars into CNF. i. S --> abAB, A --> bAB/?, B --> Baa/A? ii. S --> Aba, A --> aab, B --> Ac Q5. Convert the following grammars into GNF. i. S --> AB b/a, A --> aaA/B, B --> bAb ii. S --> ab/aS/aaS Q6. Determine whether the string W = aabbb is in the language generated by the grammar S --> AB, A --> BB/a, B --> AB/b Q7. Construct an npda for the languages: i. L = {W belongs to {a, b} * / na(w) = nb(w) } ii. L = {WWR / W? belongs to{a, b} *} iii. L = {anb2n /n > 0} iv. L = {ambn / m < n < 2m} Q8. Construct an npda corresponding to the grammar: S --> aABB / aAA A --> aBB/a, B --> bBB/A Q9. Find a CFG that generates the language accepted by the npda M = [{q0, q1}, {a, b}, {A, Z}, S, F0, Z, {q, z}] with transitions: S(q0, a, z) = {q0, AZ)} S(q0, b, A) = {q0, AA)} S(q0, a, A) = {q1, ?) Q10. Prove that the following languages are not CFL: i. {an! / n > 0} ii. {ww / w belongs to {a, b} * } iii. {anbj / n < j2} Contd… iv. {W E {a, b, c} * /na(w) = nb(w) = nc(w)} Q11. Show that the family of context – free languages is closed under: i. homomorphism ii. reversal Q12. Give an example of a CFL whose complement is not context free. Q13. Let L = {ai bj cj di / i, j belong to N} a. Find a pda (which via final state) that recognizes L b. Is there a DPDA that recognizes L. c. Find a grammar equivalent to the pda in part (b). Q14. Give reasons why one might conjective that the following language is not deterministic: L = {an bm ck / n = m or m = k} Q15. Show that the following languages are deterministic context – free languages: i. {an b2n / n > 0} ii. {W belongs to {a, b} * / na (w) < nb (w)} * * * * * |