CS 162--Formal Languages and Automata Theory Final

1. (30 points). Short Answers.

(a) Draw an example of a DFA having just 1 state, over the alphabet {0, 1} that accepts an infinite number of strings.

(b) Give a definition for regular expression, over an alphabet Σ, including the null string, ε, and to allow for the emptyset symbol, ∅.

(c) How can you tell if the language for a DFA is empty or not?

2. (30 points). More Short Answers.

(a) What is the Church-Turing thesis?

(b) What is the Halting problem?

(c) Draw a Venn diagram that shows the known relationships between the following set of languages: P, NP, PSPACE, regular languages, decidable languages.

3. (30 points). Draw a DFAs recognizing each of the following languages, over the alphabet

Σ = {0, 1}.

(a) {w | w contains at least three 1’s}

(b) {w | w contains at exactly two 0’s}

(c) {w | w contains the substring 011}

4. (30 points). Give a context-free grammar (CFG) for each of the following languages, over the alphabet Σ = {0, 1, 2}.

(a) {0 i1 j2 n | i, j, n ≥ 1 and i + j = n}

(b) {w | w = w R, that is, w is a palindrome}

5. (30 points). Consider the following context-free grammar:

S → S+T | T

T → T*F | F

F → (S) | a

(a) Give a derivation for the string, (a+a)*a.

(b) Draw a parse tree for the string, (a+a*a).

6. (30 points). Pumping Lemma.

(a) State the Pumping Lemma for regular languages.

(b) Use the Pumping Lemma for regular languages to show that the following language is not regular: {0 n1 n | n ≥ 0}.

7. (30 points). Consider the following two languages:

A = {(M, w) | M is a Turing machine and M accepts input w}

H = {(M, w) | M is a Turing machine and M halts on input w}.

Use the fact that A is undecidable to show that H is undecidable.

8. (30 points).

(a) Define the complexity class, NP.

(b) Define the term “NP-complete.”

(c) Define INDEPENDENT-SET as the problem that takes a graph G and an integer k and asks if G contains an independent set of vertices of size k. That is, G contains a set W of vertices of size k such that, for any u and v in W, there is no edge (u, v) in G. Show that INDEPENDENT-SET is NP-complete (remember that there are two parts to this). You may assume the NP-completeness of either VERTEX-COVER or 3SAT for the sake of this proof.

9. (30 points). Suppose you are given a DFA, A, which recognizes a language, L, and a DFA, B, which recognizes a language, M. Describe an algorithm for using the descriptions of A and B to produce a DFA, C, that recognizes the language L − M, that is each string in L that is not also in M.