(SEM IV) THEORY EXAMINATION 2022-23 THEORY OF AUTOMATA AND FORMAL LANGUAGES

SECTION A 

Section A requires brief descriptive answers for basic concepts like grammar, ε-closure, Arden’s theorem, Kleene’s theorem, Chomsky hierarchy, pumping lemma, PDA structure, halting problem, and linear bounded automata. Each answer must be a small paragraph explaining the meaning and purpose of the concept.

Extra sample questions:
Explain the meaning of deterministic finite automaton.
Describe regular expressions in short.
What is the role of a transition function in FA?

SECTION B 

Section B contains medium descriptive questions where one full paragraph is needed. These questions deal with designing automata, converting grammars, constructing PDA, CNF conversion, and understanding theoretical models like Church’s thesis and recursive languages. Answers must explain the process logically in a clear paragraph.

Extra sample questions:
Describe the steps to convert an NFA to a DFA.
Explain ambiguity in context-free grammars with an example.
Write a descriptive note on deterministic pushdown automata.

SECTION C 

Section C contains long questions involving construction, conversion, minimization, proof, CFG generation, PDA design, and Turing Machine design. Your answer must be a strong descriptive paragraph explaining the method or proof in detail.

Extra sample questions:

Explain the working of a Turing Machine with a simple example.
Describe the concept of closure properties for CFLs.
Explain how to design a TM for palindromes.