t***@engmail.uwaterloo.ca
2004-06-21 22:28:49 UTC
For anyone that wants to check their Spring 2002 midterm answers, these are
the answers I got. I've checked them with one other person and corrected the
mistakes that I found. I haven't shown the answers to the drawing questions,
since I don't have a scanner, or the answers to question 28, since we've
already seen them.
1:d, 2:d, 3:e, 4:c, 5:a, 6:b, 7:d, 8:e, 9:a, 10:d, 11:c, 12:c, 13:e, 14:b,
15:e, 16:b, 17:c, 18:c, 19:e, 20:d.
21.
a)
registers 2, 5, 8, and 10
b) Assume convention is that left-most parameter is at the top of the stack.
addi $30, $30, -8
sw $4, 0($30)
sw $5, 4($30)
jal mystery
add $6, $1, $0
addi $30, $30, 8
22.
a) Assume BODY does not take parameters on the stack (otherwise restored regs
will mess it up)
hello:
addi $30, $30, -16
sw $2, 0($30)
sw $10, 4($30)
sw $13, 8($30)
sw $15, 12($30)
BODY
lw $2, 0($30)
lw $10, 4($30)
lw $13, 8($30)
lw $15, 12($30)
addi $30, $30, 16
jr $31
b)
sll $9, $4, 2
add $9, $9, $3
lw $9, 0($9)
23.
a)
sll $1, $7, 2
sub $1, $8, $1
blez $1, false
sub $1, $8, $9
blez $1, true
false:
add $4, $0, $0
j done
true:
addi $4, $0, 1
done:
b)
bne $2, $3, skip
j distantLabel
skip:
c)
bne $2, $3, skip
llo $1, distantLabel
lhi $1, distantLabel
jr $1
skip:
24.
a)
This describes the language of all words containing balanced a's and b's (that
is, balanced in the expected manner of parentheses, brackets, braces, etc.).
This is not regular because it cannot be recognized by any DFA. At any point
in reading the expression, the DFA's state would have to at least uniquely
determine the number of as-yet-unclosed a's (including other things), but the
number of unclosed a's seen so far during a word in this language is
unbounded, and hence no finite number of states can uniquely determine that
number. Therefore a deterministic FINITE automaton can't recognize this
language, and it isn't regular.
b)
N* can't be a language, because then N would be its alphabet, and alphabets
must be finite sets. The set of natural numbers isn't finite.
c)
First, prove trivially that the base cases for regular expressions (single
symbols, the empty set, and the empty string) each have CFG equivalents. Then
prove that for each of the ways to construct regular expressions from other
regular expressions (which are concatenation, alternation, and repetition)
there exists a way to construct a CFG from the CFG equivalents of the regular
expressions used which matches the same language. i.e. concatenation of R1 R2
would be <s> -> <R1><R2>, alternation of R1 R2 would be <s> -> <R1>, <s> ->
<R2>, and Kleene of R1 would be <s> -> <R1><S>, <s> -> epsilon. Since regular
expressions are finite, you can recursively construct a CFG which matches the
same language as any regular expression, and hence all regular languages are
context-free.
d)
Show that there is at least one counter-example. For example, the language
described by the CFG from (a) is context-free, because it can be specified by
a CFG, but it is not regular, so not all context-free languages are regular.
25.
a)
(aa)*ab(aa)*|(aa)*ba(aa)*
b)
No.
Yes.
No.
Yes.
No.
Yes.
26.
b)
We know this because
(1) there is a process to turn any regular expression into an epsilon-NFA
which matches the same language,
(2) there is a process to turn any epsilon-NFA into an NFA which match the
same language,
(3) there is a process to turn any NFA into a DFA which matches the same
language,
and (4) there is a process, not discussed in this course, to turn any DFA into
a regular expression.
By (1), (2), and (3), every language matched by a regex is matched by some
DFA, and by (4) the converse is also true, so the languages are equal.
27.
b) 2^n - 1
c) For each non-empty subset of the n states, the NFA can reach a set of
internal states which equals that subset.
d) n
e) Each NFA state has only one transition for each possible symbol - i.e. it's
already a DFA.
----------------------------------------
This mail sent through www.mywaterloo.ca
the answers I got. I've checked them with one other person and corrected the
mistakes that I found. I haven't shown the answers to the drawing questions,
since I don't have a scanner, or the answers to question 28, since we've
already seen them.
1:d, 2:d, 3:e, 4:c, 5:a, 6:b, 7:d, 8:e, 9:a, 10:d, 11:c, 12:c, 13:e, 14:b,
15:e, 16:b, 17:c, 18:c, 19:e, 20:d.
21.
a)
registers 2, 5, 8, and 10
b) Assume convention is that left-most parameter is at the top of the stack.
addi $30, $30, -8
sw $4, 0($30)
sw $5, 4($30)
jal mystery
add $6, $1, $0
addi $30, $30, 8
22.
a) Assume BODY does not take parameters on the stack (otherwise restored regs
will mess it up)
hello:
addi $30, $30, -16
sw $2, 0($30)
sw $10, 4($30)
sw $13, 8($30)
sw $15, 12($30)
BODY
lw $2, 0($30)
lw $10, 4($30)
lw $13, 8($30)
lw $15, 12($30)
addi $30, $30, 16
jr $31
b)
sll $9, $4, 2
add $9, $9, $3
lw $9, 0($9)
23.
a)
sll $1, $7, 2
sub $1, $8, $1
blez $1, false
sub $1, $8, $9
blez $1, true
false:
add $4, $0, $0
j done
true:
addi $4, $0, 1
done:
b)
bne $2, $3, skip
j distantLabel
skip:
c)
bne $2, $3, skip
llo $1, distantLabel
lhi $1, distantLabel
jr $1
skip:
24.
a)
This describes the language of all words containing balanced a's and b's (that
is, balanced in the expected manner of parentheses, brackets, braces, etc.).
This is not regular because it cannot be recognized by any DFA. At any point
in reading the expression, the DFA's state would have to at least uniquely
determine the number of as-yet-unclosed a's (including other things), but the
number of unclosed a's seen so far during a word in this language is
unbounded, and hence no finite number of states can uniquely determine that
number. Therefore a deterministic FINITE automaton can't recognize this
language, and it isn't regular.
b)
N* can't be a language, because then N would be its alphabet, and alphabets
must be finite sets. The set of natural numbers isn't finite.
c)
First, prove trivially that the base cases for regular expressions (single
symbols, the empty set, and the empty string) each have CFG equivalents. Then
prove that for each of the ways to construct regular expressions from other
regular expressions (which are concatenation, alternation, and repetition)
there exists a way to construct a CFG from the CFG equivalents of the regular
expressions used which matches the same language. i.e. concatenation of R1 R2
would be <s> -> <R1><R2>, alternation of R1 R2 would be <s> -> <R1>, <s> ->
<R2>, and Kleene of R1 would be <s> -> <R1><S>, <s> -> epsilon. Since regular
expressions are finite, you can recursively construct a CFG which matches the
same language as any regular expression, and hence all regular languages are
context-free.
d)
Show that there is at least one counter-example. For example, the language
described by the CFG from (a) is context-free, because it can be specified by
a CFG, but it is not regular, so not all context-free languages are regular.
25.
a)
(aa)*ab(aa)*|(aa)*ba(aa)*
b)
No.
Yes.
No.
Yes.
No.
Yes.
26.
b)
We know this because
(1) there is a process to turn any regular expression into an epsilon-NFA
which matches the same language,
(2) there is a process to turn any epsilon-NFA into an NFA which match the
same language,
(3) there is a process to turn any NFA into a DFA which matches the same
language,
and (4) there is a process, not discussed in this course, to turn any DFA into
a regular expression.
By (1), (2), and (3), every language matched by a regex is matched by some
DFA, and by (4) the converse is also true, so the languages are equal.
27.
b) 2^n - 1
c) For each non-empty subset of the n states, the NFA can reach a set of
internal states which equals that subset.
d) n
e) Each NFA state has only one transition for each possible symbol - i.e. it's
already a DFA.
----------------------------------------
This mail sent through www.mywaterloo.ca