Theoretical Computer Science MCQ
|
1. Introduction |
1. Introduction
1. Symbol, Alphabet, String, Prefix & Suffix of Strings, Formal Language, Operations on Languages.
2. Regular Expressions (RE) : Definition & Example
3. Regular Expressions Identities.
|
MCQ Link1 MCQ Link2 |
|---|---|---|
|
2. Finite Automata |
2. Finite Automata 1. Deterministic finite Automaton – Definition, DFA as language recognizer, DFA as a pattern recognizer.
2. Nondeterministic finite automaton – Definition and Examples.
3. NFA TO DFA : Method
4. NFA with ε- transitions Definition and Examples.
5.NFA with ε-Transitions to DFA & Examples
6. Finite automaton with output – Mealy and Moore machine, Definition and Examples.
7. Minimization of DFA, Algorithm & Problem using Table Method.
|
MCQ Link1 MCQ Link2 MCQ Link3 MCQ Link4 |
|
3. Regular Languages |
3. Regular Languages
1. Regular language-Definition and Examples.
2. Conversion of RE To FA-Examples.
3. Pumping lemma for regular languages and applications.
4. Closure properties of regular Languages
(Union, Concatenation, Complement, Intersection and Kleene closure)
|
MCQ Link1 |
|
4. Context Free Grammar and Languages |
4. Context Free Grammar and Languages
1. Grammar - Definition and Examples.
2. Derivation-Reduction - Definition and Examples.
3. Chomsky Hierarchy.
4. CFG : Definition & Examples. LMD, RMD, ,Parse Tree
5. Ambiguous Grammar : Concept & Examples.
6. Simplification of CFG :Removing Useless Symbols, Removing unit productions, Removing є productions & Nullable symbols
7. Normal Forms :Chomsky Normal Form (CNF) Method & Problem, Greibach Normal form (GNF) Method & Problem
8. Regular Grammar : Definition.
i) Left linear and Right Linear Grammar-Definition and Example. ii) Equivalence of FA & Regular Grammar : Construction of regular grammar equivalent to a given DFA, Construction of a FA from the given right linear grammar
9. Closure Properties of CFL’s(Union, concatenation and Kleen closure) Method and examples
|
MCQ Link1 |
|
5. Push Down Automaton |
5. Push Down Automaton 1. Definition of PDA and examples
2. Construction of PDA using empty stack and final State method : Examples using stack method
3. Definition DPDA & NPDA, their correlation and Examples of NPDA
array elements.
4. CFG (in GNF) to PDA : Method and examples
|
MCQ Link1 |
|
6. Turing Machine |
6. Turing Machine
1. The Turing Machine Model and Definition of TM
2. Design of Turing Machines
3. Problems on language recognizers.
4. Language accepted by TM
5. Types of Turing Machines(Multitrack TM,Two way TM, Multitape TM,Non-deterministic TM)
6. Introduction to LBA (Basic Model) & CSG.
7. Computing TM, Enumerating TM, Universal TM
8. Recursive Languages :
i) Recursive and Recursively enumerable Languages. ii) Difference between recursive and recursively enumerable language.
9. Turing Machine Limitations
10. Decision Problem, Undecidable Problem, Halting Problem of TM
|
MCQ Link1 |
