CMPSC 464: Introduction to the Theory of Computation (Spring 2020) (Time: 8 PM – 10 PM) Practice Midterm 2
Instructor: Mahdi Belbasi
Date: 03/01/2020
Name ——————————– PSU Email ————————- Section (001 or 002?) ————
This is an OPEN BOOK, and ONLINE exam but YOU ARE NOT ALLOWED TO GET HELP FROM INTER- NET, OTHERS, OR ANY OTHER RESOURCE RATHER THAN THE BOOK AND ALL THE MATERIAL UPLOADED BY US ON CANVAS!
We’ll release the problem set exactly at 8 pm. You’ll download the problem set (the version that we tell you one day before the exam) from Canvas. Then write the answer for every problem in a separate A4 paper (you can also write with a tablet. Other papers are also fine if you don’t have A4) (do not forget to mention problem number on top of the page). You have 2 hours to answer the questions (till 10 pm). I also give you 15 more minutes to scan the answers. Then use a scanner or a good camera to make an electronic copy of your submission (like what you do for homework).
There is NO “I go for 25%” in the exam.
Remember, we all have agreed to respect academic integrity.
Don’t forget to mention the version number. If you answer the wrong version, you will get 0. Good Luck!
Problem Possible Points 1
2 3 4 5 6
Total 100
14
10
20
15
30
11
1
Introduction to the Theory of Computation (Spring 2020) – Mahdi Belbasi – Practice Midterm 2 2
Problem 1 (2 + 2 + 2 + 2 + 2 + 2 + 2 points)
Answer True/False (you don’t need to give justification).
(a.) The intersection of two uncountable sets can be finite.
(b.) Let L be a language. If there exists a number p such that for every string w ∈ L where |w| ≥ p, w can be divided into 5 pieces uvxyz such that
• ∀i≥0:uvixyiz∈L, • |vxy| ≤ p, and
• |vy| > 0,
then L is a context-free language.
(c.) The set of complex numbers is countable.
(d.) Let A be a context-free language, then its complement is not necessarily context-free but it is for sure decidable.
(e.) A valid Turing machine should always halt after a finitely many steps.
(f.) Two DFAs X and Y are equivalent if and only if L(X) ∩ L(Y ) = ∅.
(g.) Let w be a string generated by a CFG in Chomsky normal formal, where |w| = n > 2. It is possible that every derivation of w has at least n2 − 1 steps.
Introduction to the Theory of Computation (Spring 2020) – Mahdi Belbasi – Practice Midterm 2 3
Problem 2 (10 points)
Convert the CFG G = ({S, A, B, X, T }, {1, 5, 8, 0}, R, S) to an equivalent PDA, where R is as follows:
S → AX0B1T | 15B8A A → AA01XT | ε
B → BB | 101
X → T 5A | T X T → X0B
Prove that the language L = {xyz | x, z ∈ Σ∗ and y ∈ Σ∗1Σ∗1Σ∗, where |x| = |z| ≥ |y|} is not context- free, where Σ = {0, 1}.
Write-once Turing machine is a single-tape Turing machine that can change each tape cell at most once. Show that this variant Turing machine is equivalent to the ordinary Turing machine.
Formulate each of the following problems as a language and then prove that the corresponding languages are decidable
(a) The problem of checking if a PDA recognizes an infinite language.
(b) The problem of checking if the language described by regular expression A is a subset (subset or equal: ⊆) of the language described by regular expression B.
Show that the set of all infinite sequences over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is uncountable.
Problem 3 (20 points)
Problem 4 (15 points)
Problem 5 (15 + 15 points)
Problem 6 (11 points)