Final Exam - Fall 2023-Solution TOA

National University of Computer and Emerging Sciences, Lahore Campus
Course: Theory of Automata Course Code: CS-3005

Program: BS (Computer Science) Semester: Fall 2023
Duration: 180 Minutes Total Marks: 60
Paper Date: 27-December-2023 Weight 40 %
Section: ALL Page(s): 12
Exam: Final Term Roll No.
Instruction/Notes: 1. Answer in the space provided, showing all the steps.
2. You can take rough Sheets but will not be collected.
3. In case of confusion or ambiguity make a reasonable assumption.
4. Attempt all Questions
CLO 1 CLO 2 CLO 3 CLO 4
a b c Total a b Total a b Total a b Total
3 1 8 12 2 10 12 4 8 12 10 14 24
CLO 1 [3 + 1 + 8 =12 Marks]
Question 1:
a) If L1, L2 and L3 are Context free languages and L4 = L1 Ո (L2 U L3). What kind of language will
be L4. (RL, CFL or non-CFL) Explain briefly [3 Marks]
Non CFL
L2 U L3= CFL
L1 Ո (L2 U L3)= Non CFL
b) True/ False Context free languages are closed under difference. [1 Marks]
False
FAST School of Computing Page 1

c) 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 + 6 = 8 Marks]
L = {ai bj ci d(i+j) : i, j ≥ 0}
same approach we discussed during the class.

CLO 2 [2 + 10 =12 Marks]
Question 2:
a) Tick all regular expressions which express [2 Marks]

L = {w | w  {0,1}* and w has no consecutive 0 and no consecutive 1}
a. (10)*+(01)*
b. (10 + 01)*
c. (0(10)* + 1(01)*)*
d. None of these
b) Minimization of DFA [5 Marks]

Find a minimum-state DFA recognizing the same language. Show complete working. Use only the
method discussed in your respective classes.
Minimal DFA

CLO 3 [4 + 8 =12 Marks]
Question 3:
a) Tell whether the following grammar is ambiguous. How? Give justification [2+2 = 4 Marks]
S 0S1 |0S11 |∧
Ambiguous
Justification: two LMD OR 2 RMD from same string WITH EXAMPLE
b) The Html Table Creator [6 + 1.5 = 7.5 Marks]
Statement: Sample HTML Code

Consider a context-free grammar that generates Strings in a specific <table>
format to create an HTML table. The grammar produces a table with
<tr>
rows%3=0 contains Numbers only, where all other rows can contain
<td>2<\td>
a Number or Alphabet. The goal is to design a grammar that <td>4<\td>
generates valid HTML code for such a table structure. <\tr>
<tr>
<td>A<\td>
Sample Output: <td>5<\td>
<\tr>
2 4 <tr>
A 5 <td>1<\td>
<td>D<\td>
1 D <\tr>
8 9 <tr>
<td>8<\td>
<td>9<\td>
<\tr>
<\table>

Design a context-free grammar that generates HTML code for a table with rows%3=0. The multiple of 3
rows should display numbers in each cell, while all the other rows should display alphabet or number.
Each row should have at least one cells/columns. Table must contain at least one row. So the minimum
number of rows and columns could be a single cell that is one row and one column. Your CFG can have
variable number of cells/columns for each row. The generated HTML code should follow the standard
syntax and structure of an HTML table. For the context-free grammar, you need to define the production
rules that generate the HTML code for the desired table structure. Consider the use of non-terminal
symbols for different components of the HTML code, such as the <table>, <tr>, <th>, and <td> tags, as
well as the number and alphabet elements. You can use this scenario to design and explore the grammar
rules that would generate the desired HTML table structure.

Solution: [Write a CFG for the above scenario also derive the Sample Output [up to 2 rows only] from
your CFG using Parse Tree]
CFG:
S → < table > R0 </table > S | < table > R0 </table >
R0 → < tr > C0 </tr > R1 | < tr > C0 </tr >
R1 → < tr > C1 </tr > R2 | < tr > C1 </tr >
R2 → < tr > C1 </tr > R0 | < tr > C1 </tr >
C0 → < td > Num </td > C0 | < td > Num </td >
C1 → < td > Num </td > C1 | < td > Num </td >
C1 → < td > Alpha </td > C1 | < td > Alpha </td >
Num → 0|1|2|3|4|5|6|7|8|9|0
Alpha → a|b| ... |z|A|B ... |Z

Parse Tree:
CLO 4 [10 + 14 =24 Marks]
Question 4:
a) Suppose you have a single tape Turing machine (TM) that is infinite from both ends. The current
head (pointer) is at # (in the start of TM). Dry run the TM on next page and give the content of the
tape after running it (When TM halts). Also mention the location of the head [8.5+1.5 = 10
Marks]
Input String:
. . . ∆ ∆ # ∆ 1 0 ∆ ∆ ∆ . . .
Final Output along with head/pointer Location

∆∆1111#∆XXX11111111∆∆
pointer: ∆ after hash

b) Design a Multi-Tape Turing Machine that has two inputs X and Y. Both inputs are unary numbers.
X is placed on tape 1 while Y is on tape 2. You need to perform X mod Y and store its remainder
and quotient in Tape 3 and Tape 4 respectively. Sample input and output is given below. [14 Marks]
Note: X and Y are greater than 0.
Sample Input:
Tape1 ∆ 1 1 1 1 1 ∆
Tape2 ∆ 1 1 1 ∆ ∆ ∆
Tape3 ∆ ∆ ∆ ∆ ∆ ∆ ∆
Tape4 ∆ ∆ ∆ ∆ ∆ ∆ ∆
Sample Output:
Tape1 ∆ 1 1 1 1 1 ∆
Tape2 ∆ 1 1 1 ∆ ∆ ∆
Tape3 ∆ 1 1 ∆ ∆ ∆ ∆
Tape4 ∆ 1 ∆ ∆ ∆ ∆ ∆
Turing Machine

Rough Work


Final Exam - Fall 2023-Solution TOA

Uploaded by

Copyright:

Available Formats

Final Exam - Fall 2023-Solution TOA

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

Final Exam - Fall 2023-Solution TOA

Uploaded by

Copyright:

Available Formats

National University of Computer and Emerging Sciences, Lahore Campus

Course: Theory of Automata Course Code: CS-3005

CLO 1 CLO 2 CLO 3 CLO 4

a b c Total a b Total a b Total a b Total

CLO 1 [3 + 1 + 8 =12 Marks]

FAST School of Computing Page 1

same approach we discussed during the class.

FAST School of Computing Page 2

a) Tick all regular expressions which express [2 Marks]

b) Minimization of DFA [5 Marks]

FAST School of Computing Page 3

b) The Html Table Creator [6 + 1.5 = 7.5 Marks]

Statement: Sample HTML Code

FAST School of Computing Page 6

FAST School of Computing Page 7

FAST School of Computing Page 8

CLO 4 [10 + 14 =24 Marks]

Final Output along with head/pointer Location

FAST School of Computing Page 9

pointer: ∆ after hash

FAST School of Computing Page 10

FAST School of Computing Page 12

FAST School of Computing Page 14

You might also like