1. 2. 3. 4.
6. 7. 8. 9.
If A is a DFA with n states and it accepts all strings of length < n, then A accepts all strings.
The language L = {ww|w is an element of {a, b}∗} is regular.
For regular expressions r and s, we have that L((r|s)∗) ⊆ L(r∗|s∗).
To derive a string of length n in a grammar in Chomsky normal form, one needs to use exactly 2n − 1 productions.
If P is a PDA where no transition changes the number of symbols on the stack, then the language that P accepts by final state is regular.
ThegrammarS→bSb|A A→aA|bisambiguous.
If a language L is the union of two undecidable languages, then L is undecidable itself. It is decidable whether a Turing machine accepts the empty string.
Given an example of a language L1 and a Language L2 such that
• L1 is not NP-complete, but L2 is NP-complete • The union of L1 and L2 is not NP-complete
• The intersection of L1 and L2 is NP-complete.
If the language L is in NP, then the complement of L is in PSPACE.
Finite Automata and Regular Languages (15 credits)
ANU COMP3630: Final Exam 2020
May 27, 2022
For each of the statements below, determine whether it is true or false, and justify your answer in at most two sentences.
Let L be a regular language. Show that the set of all strings w ∈ L that are of odd length is also a regular language. Does the same also hold for the strings of even length?
3 Context Free Languages and Pushdown Automata (20 credits)
Consider the language L = {wcx | w,x ∈ {a,b}∗,w ̸= x} over the alphabet Σ = {a,b,c}. Is the language L context free? Either give a proof of L being context free, or a proof of L not being context free.
Computer Science Tutoring
4 Turing Machines and Recursive Languages (15 credits)
A useless state of a deterministic Turing machine M is a state q that the machine never enters on any input. In other words, q is useless if for all strings w, running M on input w never causes the TM to enter state q.
Show that the problem of determining whether a (deterministic) TM M has a useless state is undecidable.
5 Complexity (20 credits)
Let TWO be the problem of deciding whether a boolean formula in 3-CNF has at least two different variable assignments under which it evaluates to true.
Show that TWO is NP-complete.
CS Help, Email: tutorcs@163.com