Date: 15/06/2021
Duration: 2:00 Hrs
Marks: 40
No. of pages including cover: 9
Final Exam
Semester: Spring 2020 / 2021
Faculty : Faculty of Science
Department : Math and Computer Science Division/ Program: Computer Science
Course Name : Theory of Computation Course Code: CMPS 346
Student's Name: …………………………….……………………….………...….……………… ID: ……………………………….……….….…….….……………….
Section/ Group: ………………………...…..….…….….……………………….….…………… Seat Number: ……………………………………………..
INSTRUCTIONS:
1- Any kind of cheating will subject the student to the penalties specified by the University rules
2- Use of cell phone is strictly prohibited
3- One A4 Cheat Sheet ‘Handwritten’ Is Allowed
Question Mark Out of
One 6 Total marks in letters
Two 4
Three 6
Four 4
Five 6
Six 10
Seven 4
BONUS 3 Examiner’s Name: Dr. May Itani
Signature: …………………………….……………….……………….…..….…….
Total 40
1/9
Question 1: Short Answer (6 points):
I. True or False:
a) A context-free grammar G is ambiguous if there is a string in L(G) that
is the yield of two different parse trees. ------------------------
------------------------------------------------------
b) If L is context-free then LR = {wR : w L} is context-free. --------------
-----------------------------------------------------------------------------------
c) If A ∩ B is context-free, and A is context-free, then B is regular.
--------------------------------------------------------------------------------------
d) The language generated by the CFG: S → aS | bS | is {a,b}*.
------------------------------------------------------------------------------------
e) A computation in a PDA must always be finite, no matter what the
input is.
-------------------------------------------------------------------------------------
II. Write Y or N in the entries of the table below to indicate which classes of
languages are closed under which operations.
Operation Regular Languages Context Free Languages
Union
Intersection
Complement
Concatenation
III. You are given the transition functions δ of a DFA & NFA.
• DFA, δ : Q × Σ → Q, where Q is the set of states and Σ is the alphabet.
• NFA, δ : Q × Σε → P(Q), where Σε = Σ ∪ {ε} and P(Q) is the power set of Q
Give the transition functions δ of a PDA, Turing machine and nondeterministic
Turing machine.
• PDA, δ :
• TM, δ :
• Non-deterministic TM, δ :
2/9
Question 2: CFLs/CFGs (4 points):
I. Show that the class of CFLs is not closed under intersection
II. Consider the following context-free grammar G.
S a|YZ
Z ZY | a
Y b | ZZ | YY
Is G in Chomsky Normal form? Justify.
Does G generate babba? If yes then show the derivation.
If No, give another string of length 5 that G generates.
3/9
Question III (6 points).
Let = {0,1}, and consider the following languages:
E = {w : w* , and | w| is even }, the set of even length strings
EP = {wwR : w* }, the set of even length palindromes, and
P = {w = wR : w* }, the set of palindromes.
a. Show that EP is not regular using the pumping lemma for regular languages
b. Using closure properties, and given that E is regular, together with the result of part (a)
above, argue that P is not regular
c. Show that EP is a context free language by giving a context free grammar that generates
it
4/9
Question IV (4 points).
Let = {0,1,#} & Consider the language A = { 0n#u | |𝑢| = n, n 0}
a. Show that A is context free by giving the state diagram of a PDA that recognizes
A, with as small a number of states as possible
b. Give a context free grammar that generates A, having as small a number of
variable symbols as possible.
Question V (6 points).
Consider the language A = { 0n#w1n | n 0, w {0,1}* }
a) List the first 6 strings of A in lexicographic order.
b) Show that A is context free by giving a CFG that generates it.
5/9
c) In the following PDA that recognizes A, fill out the missing labels in
the indicated rectangles. Also, complete the following:
Question VI (10 points).
Consider the state diagram of a Turing machine M shown next.
We have used the convention that missing arrows are arrows that would have pointed
to qreject , which is also not shown in the diagram.
6/9
a) Show the next 5 configurations in the computations of E, if the input
w=. The starting configuration is given.
w Computation sequence of first 6 configurations on w
q1
b) What is the purpose of the loop at q5 ?
c) For each input w below, determine the behavior of M on w.
Input w M will
Accept Reject Loop
0011 Accept Reject Loop
7/9
010 Accept Reject Loop
011011 Accept Reject Loop
00101101 Accept Reject Loop
d) If during the computation on a string, the machine M is in state q3 ,
what can you conclude ?
Given High-level description of M:
M = “On input w
1. Check if the input starts with a 0 or a 1, and mark the start with
2. If the start character was a 0, look for first unmarked 1; if the start
character was 1, look for the first unmarked 0. Mark it with #.
3. Mark the first unmarked character encountered.
4. Zig-zag across the input, skipping over any #’s. Find the first
unmarked counter character, and mark it.
5. If all the symbols have been marked, accept; otherwise, reject.”
e) What is the language L that M recognizes? Explain.
Question VII (4 points).
Given the following language L = {0n#0n#0n | n 0}
L is NOT context free.
a. Find the complement of L
8/9
b. Use the closure properties & another language you should define to prove
that the complement of L is context free.
BONUS (3 points)
Give a high-level description of the Turing machines that decides the following
language
L={0n1n2n | n ≥ 0}
9/9
