SE 3310bTheoretical Foundations of Software EngineeringWinter 2019Prof. EssexAssignment 1Due Friday Feb 1st, 2019Submission Instructions: Submit solutions in a single PDF via OWL. Assignments are dueat 11:59:59 pm (Eastern Time) on the date listed above. As per the course late policy, assignmentssubmitted more than 48 hours late will not be accepted and a mark of zero (0) will berecorded. Email submissions will not be accepted.1. [6 marks] Describe the languageThe 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 cq0 q1 q2 q0q1 q3 q2 q2q2 q1 q3 q1q3 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 languagesFor each of the following languages state whether it is regular or not. If Liis regular, prove itby drawing a DFA or NFA (your choice) that recognizes it. If the language is not regular, givean 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}, SE 3310b作业代做、代写Software Engineering作业、代做Python，Java，c/c++编程语n > 0}(c) [2 marks] Lc = {wxa : w, x ∈ {a, b}∗}(d) [2 marks] Ld = {wwa : w, x ∈ {a, b}∗}SE 3310b — Assignment 1 23. [10 marks] Recognizing decimal integers divisible by 5Let string s ∈ {0, . . . , 9}∗. Let n be string s interpreted as a decimal integer. Draw a DFA thataccepts s if and only if:n ≡ 0 mod 5.Assume ε 6≡ 0 mod 5.4. [6 marks] Design NFAsLet Σ = {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 ab, etc).5. [10 marks] An NFA in an Economy of StatesLet s ∈ Σ = {a}∗. Let |s| denote the length of string s. Construct a finite automaton in lessthan 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 RegularWe say a language L is finite if L contains a finite number of strings. Using induction, proveall finite languages are regular.转自：http://www.daixie0.com/contents/9/4657.html
网友评论