Thursday, November 18, 2010

TOC Question

Gujarat Technological University
Subject : 160704 – Theory of Computation

1. Strings, languages, operations, examples
2. Regular Languages and Regular Expressions. Definitions, examples
3. Finite Automata. Definition. Examples. The extended transition function, acceptance    by FA.
4. Example of a regular expression corresponding to a FA
5. Example of a FA corresponding to a regular expression
6. Distinguishable strings. Lower bound on the number of states (with a proof) in a FA. Example.
7. The proof that the language PAL is not regular
8. Acceptance of unions, intersections and complements of languages
9. NFA, definition, ±¤ for NFA, acceptence
10. Subset construction. Converting NFA to NFA. Example
11. NFA with ^-transitions. ±¤ for NFA with ^-transitions
12. Converting NFA-^ to NFA
13. Equivalence of FA, NFA and NFA-^. Examples
14. Kleene's theorem.
15. The equivalence classes and the theorem about the minimum number of states in FA
16. Example: The equivalence classes for L = f0n1njn > 0g
17. Minimal FA. Algorithm for constructing minimal FA. Example.
18. Pumping Lemma for Regular languages
19. Applications of Pumping Lemma
20. CFG. Examples & definitions
21. Union, concatenation and Kleene star of CFL
22. Regular grammars. Regular languages and regular grammars
23. Derivation tree and ambiguity
24. Unambiguous CFG for algebraic expressions
25. Unambiguous CFG for balanced strings of parentheses
26. Algorithm finding nullable variables in a CFG
27. Algorithm finding an equivalent CFG with no ¤-productions. Correctness of the algorithm
28. Algorithm finding an equivalent CFG with no unit productions.
29. Chomsky normal form. Example
30. PDA, definition, acceptance by PDA
31. PDA accepting the language of palindromes
32. Deterministic PDA. Example with balanced strings of bracket
33. Why PAL cannot be accepted by DPDA
34. Top-down PDA corresponding to a CFG. Acceptance of a given CFL by PDA
35. CFG corresponding to a given PDA
36. Pumping Lemma for CFL
37. Applications of Pumping Lemma for CFL
38. Definition Turing Machine.
39. TM for Palindrome