CS 314	Prof Steinberg	Fall 2005

Exercise Set 2

1. Let L1 be a formal language using the binary digits 0 and 1 as its
character set, such that a string is in F if and only if it has 3 or
more 1's in a row somewhere in it.  

A.  Draw a deterministic finite state automaton that recognizes L1.

B.  Write a regular expression whose language is L1.

2. Let L2 be a formal language using the lowercase letters a-z such that
a string is in L2 if and only if it has at least one of the strings
"lou"  or "out" somewhere within it. 

A. Draw a nondeterministic FSA that recognizes L2.

B. Write a regular expression whose language is L2.

C. (harder) Draw a deterministic FSA that recognises L2.  Hint:  what
information does the machine have to be able to remember about the
characters it has already seen?  E.g., consider the strings "about",
"abound", "aloud"  and "alot".  Whatever it remembers must be represented
by it the state it is in.

3.  Describe in English the language accepted by this DFSA:


|--1--\   |--\
V       \ V   \
S1  -1-> S2 -0-|
^\
| \ 0
|/

S1 is the start state and only S2 is an accepting state.

(In case the drawing is unclear, here is the transition table
currrent     next
state  char  state
S1     0     S1
S1     1     S2
S2     0     S2
S2     1     S1


4.  Describe in English the language of each of the following RE's:

A. ab*c*

B.  a*|b*

C. (ab)*

D. ab | cd

5. (hard)  There is no FSA that can accept a string if and only if it has
more 1's than 0's.  Prove this.  Hint:  doing the problems above may
help you think about this.