Practice Midterm 2
midterm代考 This is an OPEN BOOK, and ONLINE exam but YOU ARE NOT ALLOWED TO GET HELP FROM INTER- NET, OTHERS, OR ANY OTHER…
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. midterm代考
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 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 midterm代考
- ∀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.
Problem 2 (10 points) midterm代考
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 | TX
T → X0B
Problem 3 (20 points)
Prove that the language L = {xyz | x, z ∈ Σ∗ and y ∈ Σ∗1Σ∗1Σ∗, where |x| = |z| ≥ |y|} is not context- free, where Σ = {0, 1}.
Problem 4 (15 points) midterm代考
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.
Problem 5 (15 + 15 points)
Formulate each of the following problems as a language and then prove that the corresponding languages are decidable
- Theproblem of checking if a PDA recognizes an infinite
- Theproblem of checking if the language described by regular expression A is a subset (subset or equal:) of the language described by regular expression B.
Problem 6 (11 points)
Show that the set of all infinite sequences over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is uncountable.
