CS 181 Homework Week 5 solution

Description

1. [5 points] Let Σ = { a, b }. Consider the following language:
� = { ww | w ∈ Σ* }
Determine whether the complement � = ( Σ* – � ) of this language is a Finite
State Language. To prove whether � is finite state or not, you may use any
approach or combination of approaches we have discussed in class. (If this
exact fact is stated in the text, you cannot simply reference the statement in
the text.) There are several ways to do this. After you have solved it “your
way”, you might want to see how many other ways you can think of for extra
practice.
2. [2 points] Is the following grammar is ambiguous?
G = ( V, Σ, R, E ), V = { E }, Σ = { atom, +, x, (, ) } and
R = { E -> atom | E + E | E x E | ( E ) }
Briefly justify your answer.
3. [5 points] Show a CFG for the language Lists over the alphabet
Σ = { atom, (, ) }, consisting of all strings over Σ of
the following forms:
atom
list: where a list is any sequence between a matched pair of
parentheses of any number ( ≥ zero ) of atom’s or lists.
E.g., Lists contains:
atom , () , ( atom ) , ( atom atom ) , ( atom () ) , ( (atom) () ) , etc.
E.g., Lists does not contain:
)( , atom ) , ( ( ) , ε, atom ) atom , ( atom ) atom , etc.
Total: 12 points
eof