Solution

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

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 }

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:

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)

.
(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.

Algorithm:

Turing Machine

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)

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:

A B C D E F
A -
B -
C -
D -
E -
F -
Note: Use only the cell required

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.

Require Work for CFG (if needed)

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]

Rough Work

Solution

Uploaded by

Copyright:

Available Formats

Solution

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Solution

Uploaded by

Copyright:

Available Formats

National University of Computer and Emerging Sciences, Lahore Campus

Course: Theory of Automata Course Code: CS-3005

Section 1: (Short Question Answers) [25 Marks]

L = { w over Ʃ | |w| > 5 and |w| ≤ 10 } .

L = { x | x over {a, b, c} x starts and ends with same alphabet }

FAST School of Computing Page 1

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)*

FAST School of Computing Page 3

Start State = A & Final State = {A,C}

States(q) δ(q,a) δ(q,b)

FAST School of Computing Page 4

Initial configuration of 3 multi-tape TM

First time (first slide)

Second time (second slide)

FAST School of Computing Page 5

(last and 5th slide) Eventually Output will be

FAST School of Computing Page 6

FAST School of Computing Page 7

FAST School of Computing Page 8

The initial configuration of the TM is given below

Clearly show where will be the head/pointer when TM halts

FAST School of Computing Page 9

FAST School of Computing Page 11

Note: Use only the cell required

FAST School of Computing Page 12

j=1 X,A,B,C Y,B Y,B X,A,B,C

Note: Use only the cell required

'abba' belongs to Language.

FAST School of Computing Page 13

FAST School of Computing Page 14

FAST School of Computing Page 15

FAST School of Computing Page 16

You might also like

abab + baba + (a+b)aba(a+b)bab(a+b)* + (a+b)bab(a+b)aba(a+b)*