Bihar Engineering University, Patna

B.Tech 5th Semester Exam., 2025

Time: 03 HoursCode: 105503Semester: VFull Marks: 70

Q.1 Choose the correct option / answer the following (Any seven question only):[2 x 7 = 14]

Which of the following is the smallest unit in the definition of a language?
1. Grammar
2. Alphabet
3. String
4. Production
A language is a
1. Set of alphabets
2. Set of strings over an alphabet
3. Set of grammars
4. Set of automata
Which grammar type is the most powerful?
1. Type-0
2. Type-1
3. Type-2
4. Type-3
Epsilon (ε) transitions are allowed in
1. DFA only
2. Both DFA and NFA
3. NFA only
4. None
Context-Free Grammars are equivalent to
1. Finite Automata
2. Turing Machines
3. Linear Bounded Automata
4. Pushdown Automata
Pumping Lemma for CFLs is used to prove a language is
1. Not Context-Free
2. Regular
3. Decidable
4. Turing recognizable
Which of the following requires context sensitivity?
1. aⁿbⁿ
2. aⁿbⁿcⁿ
3. (a+b)*
4. a*
Recursively Enumerable languages are also called
1. Turing Recognizable
2. Turing Decidable
3. Regular
4. Context-Free
The Halting Problem is
1. Decidable
2. Undecidable
3. Context-Free
4. Regular
Which of the following is used to prove many undecidability results?
1. Pumping Lemma
2. Rice’s Theorem
3. Chomsky Normal Form
4. Subset Construction

Q.2 Solve both questions :[7 x 2 = 14]

Define the terms: Alphabet, Language, Grammar, and Derivation. Explain the relationship between them with suitable examples.
Explain Chomsky Hierarchy of languages with examples of each type and their corresponding automata.

Q.3 Solve both questions :[7 x 2 = 14]

Explain the concept of a Finite Automaton. List and describe its main components. Also, differentiate between Deterministic Finite Automaton and Non-deterministic Finite Automaton with suitable examples.
Construct a DFA that accepts all strings over {0,1} containing even number of 0s and odd number of 1s. Also, write its formal 5-tuple definition.

Q.4 Solve both questions :[7 x 2 = 14]

Convert the regular expression (a + b)abb(a + b) into an equivalent DFA. Show all steps.
Using Pumping Lemma, prove that the language L = {0ⁿ1ⁿ | n ≥ 0} is not regular.

Q.5 Solve both questions :[7 x 2 = 14]

Explain how ambiguity arises in the grammar E → E + E | E * E | id | (E). Remove the ambiguity by rewriting the grammar.
Using Pumping Lemma for CFLs, prove that L = {aⁿbⁿcⁿ | n ≥ 0} is not context-free.

Q.6 Solve both questions :[7 x 2 = 14]

Explain Linear Bounded Automata and its relationship with Context-Sensitive Languages.
Explain the basic model of a Turing Machine with its formal 7-tuple definition.

Q.7 Solve both questions :[7 x 2 = 14]

Design a Turing Machine that accepts the language L = {aⁿbⁿ | n ≥ 0}. Show the transition diagram/table and trace for input aabb.
State and explain the Church-Turing Thesis.

Q.8 Solve both questions :[7 x 2 = 14]

Explain the concept of Universal Turing Machine. How does it help in proving undecidability?
Discuss the power and limitations of Turing Machines. Compare Turing Machines with Pushdown Automata.

Q.9 Write short note on any two of the following:[7 x 2 = 14]

Formal language & automata theory