National University of Computer and Emerging Sciences, Lahore Campus
Course: Theory of Automata Course Code: CS-3005
Program: BS (Computer Science) Semester: Fall 2022
Duration: 180 Minutes Total Marks: 80
Paper Date: 17-December-2022 Weight 40 %
Section: ALL Page(s): 16
Exam: Final Term Roll No.
Instruction/Notes: 1. Answer in the space provided, showing all the work.
2. Rough Sheets are not allowed.
3. In case of confusion or ambiguity make a reasonable assumption.
4. Attempt all Questions
Section 1: (Short Question Answers) [25 Marks]
Q1: What is the cardinality of L? [3 Marks]
L = { w over Ʃ | |w| > 5 and |w| ≤ 10 } .
Σ = {0,1,2}
Note: Cardinality means the total number of elements in the given set.
88209
Q2: Design a Finite Automaton (DFA or NFA) for the following language. [3 Marks]
L = { x | x over {a, b, c} x starts and ends with same alphabet }
Note: Pick a suitable sub-category from FA and design the machine accordingly.
FAST School of Computing Page 1
FAST School of Computing Page 2
Q3: What will be the language of the following grammar? [7 Marks]
L → ALB | AABB
A → aAb | aaabbb
B → ccBd | ˄
Note: You are required to write answer in a proper format. For Example, see Q1 statement. You are
expected to write a proper answer based on CFG given above. Lengthy Statements are not required here.
Q4: Write a Regular Expression for the following Language. [4 Marks]
L = { x | x over {a, b} x contains ′aba′ and ′bab′ as a substring }
abab + baba + (a+b)*aba(a+b)*bab(a+b)* + (a+b)*bab(a+b)*aba(a+b)*
Q5: Design the transition diagram of a PDA for the following Language? [4 Marks]
L = {an bm ; n + m = even }
FAST School of Computing Page 3
Q6: What will be the Regular Expression for the following Finite Automaton? [4 Marks]
Start State = A & Final State = {A,C}
States(q) δ(q,a) δ(q,b)
A B A
B B C
C D C
D D D
Note: Use State Elimination Method for extraction of Regular Expression. Write Final Regular Expression in the
space provided below. Delete the given states in the following order, first State A then B then C & then D.
Regular Expression:
FAST School of Computing Page 4
Section 2: (Long / Detailed Solving Question Answers) [55 Marks]
Q1: Develop 3 multi-tape TM having 2 inputs X and Y (X and Y ɛ {0,1}*) [15 Marks]
X is on tape 1 and Y is on tape 2. Y slides over the X with the step of 1. Each time it computes the exclusive
nor (XNOR) of the corresponding overlapping bits and note down the number of 1’s (only) in tape 3 as
shown below:
A B A XNOR B
0 0 1
0 1 0
1 0 0
1 1 1
Truth Table for XNOR for inputs A and B
Initial configuration of 3 multi-tape TM
Tape 1:
Δ 0 1 1 1 1 0 0 Δ
X
Tape 2:
Δ 1 0 1 Δ Δ Δ Δ Δ
Y
Tape 3:
Δ Δ Δ Δ Δ Δ Δ Δ Δ
Output
Y will slide 5 times on X (in this example)
First time (first slide)
Second time (second slide)
FAST School of Computing Page 5
.
(last and 5th slide) Eventually Output will be
Provide the algorithm first that will explain your logic in simple statement and then draw TM:
Note: Be clear and to the point. Clearly mention where your pointers are. No marks if algorithm is
incorrect.
FAST School of Computing Page 6
Algorithm:
FAST School of Computing Page 7
Turing Machine
FAST School of Computing Page 8
Q2: Dry run the single-tape Turing machine on page 10 and give the content of the tape after running it
(When TM halts). [15 Marks = 10 + 5]
The initial configuration of the TM is given below
Answer:
Clearly show where will be the head/pointer when TM halts
What is TM doing? (Explain in not more than 2 lines. Be brief and to the point. No mark for stories)
FAST School of Computing Page 9
FAST School of Computing Page 10
Q3. For the DFA pictured in the figure below, use the minimization algorithm discussed in the class to find
a minimum-state DFA recognizing the same language. [10 Marks]
DFA:
Minimized DFA:
FAST School of Computing Page 11
A B C D E F
A -
B -
C -
D -
E -
F -
Note: Use only the cell required
FAST School of Computing Page 12
X -> a
Q4. Let G be the following CFG: Y -> b
𝑆 → 𝐴𝑎𝐵 | 𝑎𝐵 Z -> AX
𝐴 → 𝑎 | 𝐴𝑎 S -> ZB | XB
𝐵 →𝑏|𝐶 A -> AX | a
𝐶 → 𝑏𝐶 | 𝑎 B -> YC | a | b
C -> YC | a
Determine whether the string “abba” is a member of L(G) using CYK Algorithm. [10 Marks]
j=4 S - - -
j=3 - B,C - -
j=2 S - B,C -
j=1 X,A,B,C Y,B Y,B X,A,B,C
a b b a
Note: Use only the cell required
'abba' belongs to Language.
FAST School of Computing Page 13
Require Work for CFG (if needed)
FAST School of Computing Page 14
Q5. Tell whether the following Language is context free (CFL) or non- context free (non- CFL). If it is CFL
provide PDA else prove it using Pumping Lemma
2
𝐿 = {𝑎𝑚 𝑏 𝑚 | 𝑚 ≥ 0} [5 Marks]
FAST School of Computing Page 15
Rough Work
FAST School of Computing Page 16
