SE 3310b代做、代写Software Engineering、代做Python，Java，c/c++编程语言

日期：2020-01-05 07:55

SE 3310b

Theoretical Foundations of Software Engineering

Winter 2019

Prof. Essex

Assignment 1

Due Friday Feb 1st, 2019

Submission Instructions: Submit solutions in a single PDF via OWL. Assignments are due

at 11:59:59 pm (Eastern Time) on the date listed above. As per the course late policy, assignments

submitted more than 48 hours late will not be accepted and a mark of zero (0) will be

recorded. Email submissions will not be accepted.

1. [6 marks] Describe the language

The formal description of a DFA M is is given as follows. Let S = {q0, q1, q2, q3}, Σ =

{a, b, c}, start = q0, F = {q3}, and let δ be given by the following table:

a b c

q0 q1 q2 q0

q1 q3 q2 q2

q2 q1 q3 q1

q3 q3 q3 q3

(a) [4 marks] Give the state diagram of this machine.

(b) [2 marks] Using set builder notation, describe the language accepted by M.

2. [8 marks] Identify the regular languages

For each of the following languages state whether it is regular or not. If Li

is regular, prove it

by drawing a DFA or NFA (your choice) that recognizes it. If the language is not regular, give

an argument (in plain language) why there is no DFA or NFA that can recognize it:

(a) [2 marks] Lb = {w ∈ {0, 1}

?

: w represented as a binary integer is a power of 4}

(b) [2 marks] La = {wwwan

: w ∈ {a, b}, n > 0}

(c) [2 marks] Lc = {wxa : w, x ∈ {a, b}

?}

(d) [2 marks] Ld = {wwa : w, x ∈ {a, b}

?}

SE 3310b — Assignment 1 2

3. [10 marks] Recognizing decimal integers divisible by 5

Let string s ∈ {0, . . . , 9}

?

. Let n be string s interpreted as a decimal integer. Draw a DFA that

accepts s if and only if:

n ≡ 0 mod 5.

Assume ε 6≡ 0 mod 5.

4. [6 marks] Design NFAs

Let Σ = {a, b, c}. Draw an NFA recognizing each of the following languages:

(a) [2 marks] The set of strings that contain c’s in runs of no more than two (e.g., a, ac,

acc etc., but not accc etc.).

(b) [2 marks] The set of strings that contains 2 of the 3 possible characters (e.g., aabba,

bcbb but not aabc),

(c) [2 marks] The set of strings that contain no consecutive letters (i.e., a b cannot follow a

b, etc).

5. [10 marks] An NFA in an Economy of States

Let s ∈ Σ = {a}

?

. Let |s| denote the length of string s. Construct a finite automaton in less

than two three dozen states that recognizes the language:

L = {s : gcd(|s|, 504) ≥ 6},

where gcd(x, y) denotes the greatest common divisor between two numbers x, y.

6. [10 marks] Prove Finite Languages are Regular

We say a language L is finite if L contains a finite number of strings. Using induction, prove

all finite languages are regular.