|
代做CS 310编程、Java，Python
MID-TERM EXAMINATION
16 March 2021
Instructions
• You have 24 hours to turn in your solution which is hereby due on 17 March at 9 am. There are several
ways to provide your answers: Fill in the exam PDF and send it back, print the exam paper, fill it in
by hand, and then scan the result back to PDF, or provide your answers in a standalone document
typeset to PDF. If you choose the latter option then please provide your answers in the same order as
the questions in the exam paper.
• PDF is the only acceptable Format for submitting your answers.
• The number of marks awarded for each question appear in square brackets right after the question
number. If this were a regular exam then it would have been 90 minutes in length and the number of
marks for each question would have given you an estimate on how much time you are supposed to
spend on the respective question. However, this estimate is not terribly useful in the current format.
• To obtain full marks provide all the pertinent details.
• You are not supposed to communicate with anybody about the exam questions. Identical answers to
any question found on two or more papers will result in the complete forfeiture of the examination for all the
students involved.
• Make sure that your name and student number appear at the top of the first page of each document
that you are sending.
1 15 / 15
2 5 / 5
3 5 / 5
4 10 / 10
5 (a,b) 15 / 15
6 10 / 10
7 (a,b,c,d) 20 / 20
8 10 / 10
Total: 90 / 90 = 30 / 30
1. [15] For each question below check one answer. Your response is a priori incorrect if more
than one answer is checked.
• Which of the following statements is true:
Some deterministic Finite automata do not have equivalent regular expressions.
Some nondeterministic finite automata do not have equivalent regular expressions.
Some regular expressions do not have equivalent nondeterministic finite automata.
X The above three statements are all false.
• Which of the following statements is true:
Some finite languages are not regular.
X Some context-free languages are not regular.
Some regular languages are not context-free.
The above three statements are all false.
• Let L = (a + Aba + abba)
∗
(bb + bbb). Which of the following strings is in L:
X aaabaabb
aaaabaab
abaabbbb
None of the above strings is in L.
• The language {0
k1
2n0
3k
: k, n ≥ 1}:
is both regular and context-free
X is context-free but is not regular
is regular but is not context-free
is neither Regular nor context-free
• The language {0
2k1
n
: 0 ≤ k ≤ n} is denoted by the regular expression:
(00)∗1
∗
0
∗
(00)∗1
∗
0
∗
(001 + 000011 + 000000111)∗
X None of the above.
2. [5] Give a regular expression over Σ = {0, 1} that defines exactly all the well formed binary
numbers that are divisible by 4. A well formed binary number has no leading zeroes (except
for the number 0 itself).
ANSWER:
The number 0 is a special case, else everything must start with one and end with a double
zero. The regular expression is thus 0 + 1(1 + 0)∗00.
Page 1 of 6
3. [5] The definition of regular languages in the textbook is:
A regular language is a formal language definable using only union, concatenation,
and closure from alphabet elements, ε, and ∅.
Even if we eliminate ε from the definition we still define regular languages. Explain why.
ANSWER:
ε can be produced using ∅ and closure as follows: ∅
∗ = ε. So any occurrence of ε can be
replaced in any regular expression by ∅
∗ without changing the language being generated.
4. [10] Using the systematic method described in the course convert the nondeterministic state
transition diagram below into a deterministic state transition diagram. Label the states of
the deterministic diagram with sets of states of the nondeterministic diagram.
5. [15] Let L be the language of exactly all the strings over Σ = {0, 1} of even length that end
with the symbol 0.
(a) [10] Draw the Deterministic state transition diagram that recognizes L.
(b) [5] Give a grammar that generates the language L.
ANSWER:
We follow the conversion from finite automaton: G = ({A, B, C}, {0, 1}, R, A), where
R = { A → 0B,
A → 1B,
B → 1A,
B → 0C,
C → 0B,
C → 1B,
C → ε }
Page 3 of 6
6. [10] Draw a state transition diagram that recognizes the language (1 + 01∗0)∗
. Justify your
answer.
ANSWER:
(a) Automata for 0 and 1:
0 1
(b) Automaton for 1
∗
(from 6a):
1
ε
ε
(c) Automaton for 01∗
(from 6a and 6b):
(d) Automaton for 01∗0 (from 6a and 6c):
(e) Automaton for 0 + 01∗0 (from 6a and 6d):
(f) Automaton for (0 + 01∗0)∗
(from 6e) = the answer to the question:
7. [20] Consider the Language L = {wcwR : w ∈ {d, e}
∗}, where w
R denotes the reversal of the
string w (such that for example (abc)
R = cba).
(a) [5] Give a context-free grammar that generates L.
ANSWER:
S → dSd S → eSe S → c
(b) [5] Draw a deterministic push-down automaton that recognizes the language L.
ANSWER:
A C
d, ε 7→ d
e, ε 7→ e
c, ε 7→ ε
d, d 7→ ε
e, e 7→ ε
(c) [5] Give a derivation for the string deeceed using your grammar from Question 7a.
ANSWER:
S ⇒ dSd ⇒ deSed ⇒ deeSeed ⇒ deeceed
(d) [5] Draw a table that traces the computation of your push-down automaton from Question
7b on input dece. The table should list the current state, currently remaining input,
and current stack contents at each step of the computation. Is this string accepted by
the automaton?
ANSWER:
State Input Stack
At the end we are in a final state but the stack is not empty, so the input is rejected.
Page 5 of 6
8. [10] Let L be the language of strings over {0, 1} in which both the number of 1’s and 0’s are
multiples of 3. Is L regular? Justify your answer.
ANSWER:
Let L1 = (1 + 01∗01∗0)∗
(all strings with 3n 0’s) and L2 = (0∗ + 10∗10∗1)∗
(all strings with 3n
1’s). Both these languages are Regular (being defined by regular expressions), so L1 ∩ L2 is
regular (since regular languages are closed under intersection). However, L1 ∩ L2 = L, and
therefore L is regular.
Page 6 of 6
请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
|
