Theory of Computation – Topic wise MCQ

Regular Language Models:

Deterministic Finite Automaton (DFA),
Non-Deterministic Finite Automaton (NDFA),
Equivalence of DFA and NDFA,
Regular Languages,
Regular Grammars,
Regular Expressions,
Properties of Regular Language,
Pumping Lemma,
Non-Regular Languages,
Lexical Analysis.

Context Free Language:

Pushdown Automaton (PDA),
Non-Deterministic Pushdown Automaton (NPDA),
Context Free Grammar,
Chomsky Normal Form,
Greibach Normal Form,
Ambiguity,
Parse Tree Representation of Derivation Trees,
Equivalence of PDA’s and Context Free Grammars;
Properties of Context Free Language.

Turing Machines (TM):

Standard Turing Machine and its Variations;
Universal Turing Machines,
Models of Computation and Church-Turing Thesis;
Recursive and Recursively-Enumerable Languages;
Context-Sensitive Languages,
Unrestricted Grammars,
Chomsky Hierarchy of Languages,
Construction of TM for Simple Problems.

Unsolvable Problems and Computational Complexity:

Deterministic Finite Automaton (DFA),
NonUnsolvable Problem,
Halting Problem,
Post Correspondence Problem,
Unsolvable Problems for Context-Free Languages
Measuring and Classifying Complexity,
Tractable and Intractable Problems.

Leave a Reply

Your email address will not be published.

error: Content is protected !!
Open chat
1
Hi,how Can We Help You ?