程序代做CS代考 4200 – Formal Languages – cscodehelp代写

4200 – Formal Languages
Midterm 1
Fall 2019
Oct 4, 2019 at 2:00 – 2:50pm
Student:
1

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 1
Directions: The test is open book and open notes, but NOT open electronic devices (e.g. phone, tablets or computers). For each problem, show your work completely. Give reasons for all answers. You will not only be graded on your mathematics, but also on your presentation, organization, proper use of English, spelling, punctuation, and logic.
There are 5 problems for a total of 80 points. Problem 1
10 points
For the following regular expression, draw a finite-state automaton (may be deterministic or non-deterministic). (1∪ε∪0∗1)∗ ∪(0∗)∗ ∪1∗
Problem 2
20 points
Convert the NFA M in Figure 1 into a regular expression α such that L(α) = L(M).
Notes: Please write the final expression below (on the “Final expression:”). In page 3, show step-by-step how you derive the final expression. For each step, (1) explain which state is being removed and (2) show the resultant intermediate FA.
Figure 1: Non-deterministic finite automaton M. Here, λ denotes the empty string (equivalent to ε). Final expression:
Problem 2 continued on next page. . . 2

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 2 (continued)
Step-by-step derivations:
3

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 3
Problem 3
10 points
1. Provide an example of a regular language of your own that is not verbatim-quoted from the book or lectures (i.e. your own examples or variants of book examples are acceptable). Please explicitly list out some of its elements and briefly explain the intuition why the language is regular.
2. Similarly, provide an example of a non-regular language of your own that is not verbatim-quoted from the book or lectures (i.e. your own examples or variants of book examples are acceptable). Please explicitly list out some of its elements and briefly explain the intuition why the language is non-regular.
4

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 4
Problem 4
20 points
For the following set of strings A over alphabet Σ = {a, b, c}, demonstrate that A is regular by constructing an NFA, DFA or a regular expression.
A={w∈Σ∗ |(#a(w)) mod3=1}
Here, mod is the modulo operation. That is, the number of a’s in any string w i.e. #a(w), for every
w ∈ A, when divided by 3 would yield a remainder of 1. 1. List out 5 strings in A:
2. Provide an NFA, DFA or a regular expression below.
5

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 5
Problem 5
20 points
Alphabet Σ = {0, 1}.
(a) are the following languages regular or non-regular?
(b) if your answer is regular, please provide either a DFA, NFA or regular expression (choose only one) that recognizes the language. If your answer is non-regular, please prove it by contradiction via Pumping Lemma.
1.X={ 0n1m|m,n≥0 }
Problem 5 continued on next page. . . 6

Midterm 1 4200 – Formal Languages (Instructor: Dr. ) Problem 5 (continued) 2. Y ={xx|x∈Σ∗ and |x|≥1}
The end.
7