CS 331 Spring 2013
Assignment 1

Assignment 1 is due at 5 p.m. Tuesday, February 5. It is worth 20 points.

Procedures

This assignment may be turned in either in paper form or via e-mail.

Papers should be stapled and placed in my mailbox inside the CS Department office (202 Chapman).

E-mail should be sent to ggchappell@alaska.edu, using the subject “PA1”.

• Your answers should consist of a file containing the answers to Exercises A–G. This file (or an archive file containing it) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (20 pts total)

1. Is the type checking in C++ primarily static or dynamic? What does this mean?
    
2. Give an English description of the language generated by the following grammar, whose start symbol is \(S\).

   \[S \rightarrow x S y \, | \, A\] \[A \rightarrow st A \, | \, \varepsilon\]

   
    
3. Consider the following grammar, whose start symbol is \(S\).

   \[S \rightarrow AB\] \[A \rightarrow A c \, | \, B\] \[B \rightarrow d B \, | \, d\]

   Which of the following strings are in the language generated by this grammar?

   1. \(cdc\)
   2. \(dcdcd\)
   3. \(dcdd\)
   4. \(ddd\)
   5. \(ddddc\)
   6. \(ccc\)
   
    
4. Consider the following regular expression.

   \[(a|b)^*x|c^*\]

   Which of the following strings are matched by this regular expression?

   1. \(aaax\)
   2. \(aabbxx\)
   3. \(abc\)
   4. \(b\)
   5. \(c\)
   6. \(bax\)
   
    
5. Write a regular expression that matches every word that contains no letters other than lower-case \(a\), \(b\), and \(c\) and contains at most one \(b\). (Here, a word is any sequence of letters.)
    
6. This problem deals with the following grammar, which has start symbol \(S\).

   \[S \rightarrow X\] \[X \rightarrow XX \, | \, a\]

   1. Give a leftmost derivation for the string \(aaa\).
   2. Verify that the grammar is ambiguous by finding a string with two different parse trees.

      Your answer should consist of the string and the two parse trees.

   3. Write a non-ambiguous grammar that generates the same language as the above grammar.
   
    
7. Consider the language containing those strings consisting of a single \(a\) followed by two or more \(x\)s.

   \[\{axx, axxx, axxxx, \dots \}\]

   1. Give a regular expression that generates this language.
   2. Write a BNF grammar that generates this language.