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.
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.
Programming Help
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 Pushdown Automata (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.
Computer Science Tutoring