Formal Language & Automata Theory (Theory of Computation)
Mahatma Gandhi Central University, Bihar
B.Tech Computer Science & Engineering
Semester 5 Examination, 2025
Formal Language & Automata Theory (Theory of Computation) (CSET3135)
Assessment Questions
Formal Language & Automata Theory (Theory of Computation) (CSET3135) - 2025
Section A (MCQ)
(MULTIPLE CHOICE QUESTIONS – 05 Marks) Attempt all questions. Each question carries one mark.
- 1
Which is the most powerful model?
- 2
Palindromes of even length can be recognized by:
- 3
Which of the following is false?
- 4
According to Arden’s theorem, if R = Q + RP
- 5
Let R be a relation on the set N of natural numbers defined by n R m ⇔ n divides m. Then, R is:
Section B (Short Answer)
Write briefly in 150 words (Short Answer Questions – 05 Marks) Attempt ANY TWO questions out of the followings. Each question carries 2.5 Marks.
- 1
State and explain Arden’s theorem.
- 2
Write a note on Chomsky Hierarchy.
- 3
Define an equivalence relation with suitable example.
Section C (Long Answer)
Write in 300 Words (Long Answer Questions – 10 Marks) Attempt the questions having internal choice. Each question carries 5 marks.
- 1
Answer any ONE of the following
(a)Minimize the following automaton:
OR
(b)Explain the concept of pumping lemma for regular languages.
- 2
Answer any ONE of the following
(a)Design a DFA is a string that does not contain consecutive 1's and ends with a 1.
OR
(b)Construct a PDA for language .