CS 331 Spring 2013  >  Assignment 1

# 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.
• 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.

CS 331 Spring 2013: Assignment 1 / Updated: 5 Feb 2013 / Glenn G. Chappell / ggchappell@alaska.edu