| Quiz |
Posted
|
Given in class
|
| | 14 | Jan |
23 | Jan |
Information about quizzes:
- On the date a quiz is given, a die will be thrown by a student in
the class.
- Books and notes are put away.
- A question very similar to the chosen published question will be written
on the board.
- You have 5 minutes to answer the question.
The questions are intended to be straightforward. If you keep up with
the material in the class, almost no preparation may be necessary.
The Collaboration Policy allows you to
study
in groups for the quizzes, but you are on your own when you take the quiz.
Try to work the quiz yourself before looking at the solution.
-
Provide a context-free grammar for each of the following languages:
- The set of strings of base-8 numbers.
- The set of strings of base-16 numbers.
- The set of strings of base-1 numbers.
- Design a language that allows specification of strings of
base-1, base-8, and base-16 numbers, where numbers of a given
type can be syntactically distinguished. Provide a grammar for
this language.
- Show a derivation of
( Plus ( Plus a a ) a )
using the grammar:
E -> ( Plus E E )
| ( Minus E E )
| a
- Show all distinct derivations (trees) of
a + a + a
using the grammar:
E -> E + E
| a
- For the grammar below, describe its associated language:
A -> x A x
| lambda
- What are the difficulties associated with constructing a grammar
whose generated strings are decimal representations of irrational
numbers? How can these difficulties be resolved?