Hi,my assignment is in the attachment,could anyone could help me.I could do the assignment by myself,but my professor is very strict and I don't know whether my answeris correct,so I need sb.could give me an reliable answer so that I could check with my answer.Thanks very much!
Department of Computer Science & Software Engineering Comp5361 Discrete Structures and Formal Languages Winter 2020 Assignment 2, Part 2. Due date: Friday March 20 1. Let L1, L2 and L3 be languages over some alphabet Σ. In each part below, state the relationship between the given two languages. Are they equal, is one a subset of the other, do they have an empty or non-empty intersection? Give reasons (proof!) for your answers, and counter- examples where needed. (a) L1(L2 ∩L3) versus L1L2 ∩L1L3. (b) L∗1 ∩L∗2 versus (L1 ∩L2)∗. (c) L∗1L ∗ 2 versus (L1L2)∗. (d) L∗1(L2L∗1)∗ versus (L∗1L2)∗L∗1. 2. Construct a DFA for each of the following languages (a) All and only those strings over {a, b, c} whose symbols are in alphabetical order. For example, aaabcc and ac are to be accepted, and abca and cb should be rejected. (b) All and only those strings over {0,1} that have an even number of 0’s and the number of 1’s is a multiple of 3. (c) L = {anbmck ∶ n,m, k ≥ 0, n +m + k is even } (d) L2 = {w ∈ {a, b}∗ ∶ w does not contain aab and w ends in bb} 3. Construct an NFA for each of the following languages. (a) The set of strings over {0,1, . . . ,9}, such that the final digit has not appeared before (b) The set of strings over {0,1}, such that there are two 0’s separated by a number of positions that is a multiple of 4. Note that 0 is an allowable multiple of 4. 4. Let Σ = {a, b}. (a) Construct an NFA that accepts the strings in Σ∗ where at least one of the last two symbols is an a. (b) Convert your NFA to a DFA using the subset construction. Give the DFA both in tabular form and as a transition diagram. 5. Give a regular expression for each of the languages below. (a) {aa, ab, ba, bb} ∖ {aa, bb}. (b) {akbmcn ∶ k +m + n is odd}. (c) {w ∈ {a, b, c}∗ ∶ no symbol occurs twice in succession in w}. (d) {w ∈ {0,1}∗ ∶ 00 occurs at most twice in w}. Note: 00 occurs twice in 000 1