Department of Computer Science & IT
Mid Term Paper Solution
Course: Theory of Automata
BSCS 5th Semester (SS)
Instructor: Zainab Sehar
Date: 06-12-2024
MCQs with Correct Answers (10 Marks)
1. A Stack does two operations? → b) Push, Pop
2. The derivation is read from? → d) Both a & c (Left to Right & Only Left)
3. A PDA can be described as tuples? → c) 7
4. CFG stands for? → a) Context-Free Grammar
5. T is denoted by? → b) Set of production
6. The instantaneous description of PDA is represented by a triplet: → d) All of these
7. How many tuples are in PDA? → a) 7
8. In instantaneous description, S represents: → c) The stack contents
9. In the derivation tree, the leaf nodes are: → a) Always terminal nodes
10. If there exist more than one left or right derivation tree → a) Ambiguous
✍️Short Question Answers (10 Marks)
1. Define Automaton?
An automaton is an abstract mathematical model used to simulate a machine that accepts or
rejects strings of symbols based on predefined rules or states.
2. What is FA and its types?
FA (Finite Automaton) is a machine with finite states used to recognize regular languages.
Types:
DFA (Deterministic Finite Automaton)
NFA (Non-deterministic Finite Automaton)
3. Transition Diagram of DFA (Σ = {0,1}, accepts strings starting with 1)
(Start) q0
|
↘
1| 0
v
q1 <--------- q2
(Accepting)
States: q0, q1, q2
Start: q0
Accept: q1
Transitions:
o q0 → 1 → q1
o q0 → 0 → q2
o q1 → 0,1 → q1
o q2 → 0,1 → q2
4. Transition Diagram & Table for:
If you can clarify the missing transition or language to draw (for example: even number of 0s), I
can fill this.
5. Define Regular Expression?
A Regular Expression (RE) is a symbolic representation used to describe patterns in strings and
regular languages.
Example:
(a|b)*abb accepts all strings ending with "abb".
📄 Long Question Answers (10 Marks)
1. Kleene’s Theorem and Its Importance
Kleene’s Theorem:
Kleene’s Theorem states that:
"A language is regular if and only if it can be accepted by a finite automaton or described
by a regular expression."
Parts:
1. Every regular expression can be converted into an FA
2. Every FA can be converted into a regular expression
Why is it used in Automata?
Establishes equivalence between Regular Expressions and Finite Automata.
Helps in simplifying design of pattern recognizers.
Important for compiler design, text search, etc.
2. Transducers and Their Diagram
Definition:
A Transducer is an automaton that produces output along with accepting input. It is used for
translation or conversion from one form to another.
Types of Transducers:
Moore Machine: Output depends on current state
Mealy Machine: Output depends on current state and input
Example Diagram: Mealy Machine
States: q0, q1
Input: 0, 1
Output: x, y
0/x 1/y
[q0] -----> [q1]
^ |
| |
\---1/x---/
In the above diagram:
Input 0 at q0 gives output x and moves to q1
Input 1 at q1 gives output y and loops or moves back to q0
