COMP3630/6363 Practice Exam 1, 2020
The Australian National University June 15, 2020
1 General (3 credits each)
For each of the statements below, determine whether it is true or false, and justify your answer in at most two sentences.
Copyright By PowCoder代写 加微信 powcoder
1. For regular expressions r and s, we have that L((r|s)∗) ⊆ L((r∗s∗)∗).
2. Let A be an NFA, and let B be the NFA that arises from A by swapping accepting and non-accepting states. Then the language of B is the complement of the language of A.
3. If a regular expression does not contain the symbol ’∅’ then the lan- guage of this regular expression is never empty.
4. The language of the regular expression (∅∗)∗ is empty.
5. The language L = {ww | w ∈ {a}∗} is regular.
6. The language L = {ww | w ∈ {a}∗} is context free.
7. If L is a language, and L∗ is context free, then L is context free, too.
8. Let Σ be an alphabet with ∗ ∈ Σ and let STAR be the problem of determining whether a TM M ever writes ∗ onto the tape on input w. Then STAR is deciable.
9. Every language that is not recursive is infinite.
10. The problem 3CNFTAUT – given a boolean formula in 3-CNF, does
it valuate to true for all truth value assignments – is in P.
2 Finite Automata and Regular Languages (15 cred- its)
If L is a language, let D(L) be the set of strings that differ from a string in L at at most one position. Show that D(L) is regular if L is regular.
3 Context Free Languages and (15 credits)
Show that the language consisting of all odd-length strings w ∈ {a, b}∗ where the first, middle, and last character are the same, is context free.
4 Turing Machines and Recursive Languages (20 credits)
Recall that we write ⟨M⟩ for the coding of a Turing machine M as a string. As this coding never contains ’111’ as a substring, we use ’111’ as a separator.
Let L = {⟨M1⟩111⟨M2⟩ | L(M1) ∩ L(M2) ̸= ∅. Show that L is recursively enumerable.
Let L′ = {⟨M1 ⟩111⟨M2 ⟩ | L(M1 ) ∩ L(M2 ) = ∅}. Is L′ also recursively enumerable? Justify your answer.
5 Complexity (20 credits)
For a DFA A, let ⟨A⟩ be a coding of the DFA as a string, analogously to the encoding of a Turing machine.
Show that {⟨A⟩ | L(A) = Σ∗} ∈ P, that is, the set of DFAs that accept all strings in the language is polytime decidable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com