代做CS 310编程、Java，Python程序设计代写

日期：2021-03-18 11:24

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