CSE 520

Final

Fall 1998

Name ______________________________________________

I. Regular languages:

. Let L = (b + ab*a)*ab*

a. Draw a DFA that accepts L

b. Write a regular grammar for L

2. Context free languages:

a. Write a context free grammar for the language of all balanced parenthesis

L = { "", ( ) , ( ) ( ) , (( )), ( ) ( ) ( ), (( )) ( ) , ... }

b. Give a non-deterministic push down automata that accepts strings in the language of all balanced parenthesis.

3. a. State the pumping lemma for context free languages.

b. Show that the language L = { w Î {a,b} * , #_a(w) == #_b(w) , aab is not a substring of w } is a context free language.

4. True or False:

_____ The union of two context free languages is a context free language.

_____ The intersection of two context free languges is a context free language.

_____ Given two context free languages L1 and L2, there is an algorithm to decide whether L1 == L2.

5. a. Write a Turing machine that accepts on input a binary digit (such as 110101) and will halt in an accepting state with the digit +1 on the input tape..

b. What is the Church/Turing Thesis ?

c. What is the Cooke/Karp Thesis?

6. True or False:

_____ DTIME(T(n)) is a subset of NTIME(T(n))

_____ NTIME(T(n)) is a subset of DTIME(T(n³))

_____ DTIME(T(n)) is a proper subset of DTIME(T(n³))

7. For each language in the Chomsky hierarchy, give the type of machine that accepts strings in the language or the grammar that generates strings of the language.

8. True/False

_____ For every non-deterministic finite state machine there is a deterministic finite state machine that accepts the same language.

_____ For every non-deterministic push down automata there is a deterministic push down automata that accepts the same language.

_____ For every non-deterministic Turing machine there is a deterministic Turing machine that accepts the same language.

9. Do one of the following 2 problems:

a. Eliminate the useless symbols and productions from the grammar G=(V,T,S,P) where

V = {S,A,B,C}, T = {a,b} and P consists of the rules

S -> aS | A | C

A -> a

B -> aa

C -> aCb

b. Show that the grammar G with productions

S -> aAB

A -> bBb

B -> A | ""

is ambiguous.

10. Do one of the following 2 problems:

a. Given the following NDFA, give a DFA equivalent to this machine.

0 1 e

start: q0 {q1} {q1} {}

final: q1 {q0,q2} {q1} {q2}

q2 {} {q1} {}

b. Minimize the following PDA