| Problem |
Max points |
Max points |
Comments |
| 1 |
10 |
|
|
| 2 |
10 |
|
|
| 3 |
10 |
|
|
| 4 |
10 |
|
|
| 5 |
10 |
|
|
| 6 |
10 |
|
10*1 |
| 7 |
10 |
|
5+5 |
| 8 |
10 |
|
|
| 9 |
10 |
|
5+5 |
| 10 |
10 |
|
|
| 11 |
40 |
|
8*5 |
| |
140 |
|
|
What happens with this paper (mark one): Discard
Mail
at this address :
1. Let f be the function that associates each person on
Earth his/her height (ex pressed as an
integer number of inches ). Decide whether f is bijective or not.
2. Consider the set of all regular expressions over the
alphabet A={0, 1}. Decide whether this
set is countable or not. Prove your answer (a correct guess earns you 1/3 of the
credit for
this problem).
3. Decide whether the fol lowing argumentation is valid or
not. “The Discrete Structures class
is fun or is boring. If Discrete Structures is fun then students learn.
Therefore, if Discrete
Structures is boring students do not learn.”
4. Give an inductive definition for the set of all simple
lists over the alphabet A={a, b} with
the property that the first and the last element in each list are the same.
5. Find a regular expression for the language consisting
of strings that represent numbers in
scientific normal notation. For the exp onent you will use a caret (^). For
example, instead
of 102 you would use 10^2.
6. De termine whether the strings in the table belong to
any of the languages described by the
following regular expressions:
| RE |
1001 belongs to the language (T/F) |
110 belongs to the language (T/F) |
| 10*1* |
|
|
| (10)*+(1)* |
|
|
| (00)*1*(01)*1 |
|
|
| (00)*1*(01)*1 |
|
|
| (00)*1*(01)*1 |
|
|
7. As sume a FA described by the following state transition
table:
a) Draw the state transition diagram for this FA
b) Decide which of the following strings are accepted by
this FA
| String |
Accepted (T/F) |
| 00110 |
|
| 011 |
|
| 0000 |
|
| 11000 |
|
| ε |
|
8. Construct a finite-state machine that takes an input
string consisting of 0’s and 1’s and outputs
1 when the last two characters read are different , and 0 otherwise. Use the
Mealy
model.
9. G is a context free grammar defined by:
N = {S, A} T = {0, 1} Start symbol : S
Productions:
a) what is the language of G?
b) find a leftmost derivation of the string 00111. At each
step show the production used .
10. Find the binary single-precision representation for
9.375
11. Give a definition for:
a) Set partition
b) Symmetric relation
c) Connected graph
d) Binary tree
e) The inverse of a function
f) The grammar of a language
g) Regular Language
h) A string being accepted by a DFA
