[SOLVED] software SE 3310b Winter 2019 Theoretical Foundations of Software Engineering Prof. Essex

SE 3310b Winter 2019 Theoretical Foundations of Software Engineering 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, assign- ments 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 = {a, b, c}, start = q0, F = {q3}, and let be given by the following table:
{q0, q1, q2, q3}, =
abc
q0 q1 q2 q0 q1 q3 q2 q2 q2 q1 q3 q1 q3 q3 q3 q3
(a) (b)
2.
[4 marks] Give the state diagram of this machine.
[2 marks] Using set builder notation, describe the language accepted by M.
[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) [2marks]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:
Assume0 mod5.
4. [6 marks] Design NFAs
n0 mod5.
Let = {a, b, c}. Draw an NFA recognizing each of the following languages:
(a) [2 marks] The set of strings that contain cs 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.