S314 Fall 2007
Assignment 1

#1. Scott, Problme 2.1 a,b,c,e; Also write FSA's for parts a and e.

#2. (From Aho, Sethi, Ullman, Compilers, Ch 3, #3.7)

   Write a regular expression for the following language:
     All strings of letters that contain the five vowels in order.

   Write a regular expression for the following language: 
     All strings of 0's and 1's that do not contain the substring 011.

   Show the FSA corresponding to these two regular expressions
   (note: this might be a nondeterministic FSA).

#3. Choose from among the strings {101, 11001, 1001, 0011, 10} 
    those that are in language defined by the regular expression:

     (0|1)*0(0|1)(0|1)

    If a string is contained in this language, identify which parts of
    the regular expression generate which substrings of that string.

#4. Assume you have a language with binary operators $, @, and %.
    Expressions in this language may contain variables  that consist
    of one lower case letter and single digit constants.

 a. Give a context-free grammar in BNF which implements the following 
    associativity and precedences"

        $,@ left associative;  % right associative;

        $ weakest precedence, % stronger precedence, @ strongest precedence

 b. Give the parse tree and abstract syntax tree generated by your
    grammar for the expression: a$b$1%3@5%a$d.