CS375 Homework Assignment 4-1 (22 points)
Due date: 9/24/2022
1. Given the following DFA, to find a minimum-state DFA, (7 points)
Copyright By PowCoder代写 加微信 powcoder
we first construct = {{0,3}, {1,2,4}} as follows.
consists of two components, the set of non-final states {0, 3}, and the set of final states {1, 2, 4}. We then construct . Which one in the following four cases is the correct ? Put your answer in the following box.
(a) (b)
(b) (d)
Next we construct . Which one in the following four cases is the correct ? Put your answer in the following box.
(a) (b)
(c) (d)
Since , the states of the minimum-state DFA are:
(you don’t need all these blanks)
The start state is: (1 point)
The final state is: (1 point)
2. Let the set of states for a DFA be S = {0, 1, 2, 3, 4, 5}, where the start state is 0 and the final states are 1, 3 and 5. Let the equivalence relation on S for a minimum-state DFA be generated by the following set of equivalent pairs of states:
{ (0, 4), (3, 1) }
The states of the minimum-state DFA are: (2 points)
{0.4} {1,3} {2} {5} (set notations)
(Equivalence class notations)
You only need to answer one of the above two cases.
3. Given the following regular expression over the alphabet {a, b},
a(ab)* + (ba)*b
to transform it to a regular grammar, we first transform it to an NFA as the one shown below.
Instead of converting this NFA to a regular grammar directly, we convert it to a DFA first and then convert the DFA to a regular grammar (why?). So we construct Ʌ-closures of the above NFA,
and build the following tree, (3 points)
so that the following nodes of the tree can be used to build a DFA. Fill out the following blanks and blanks in the above tree. (2 points)
4. With the selected nodes from the above tree, we build a DFA by constructing the following transition table (the table on the left), and renaming the states as S (start state), I, J, K, L, M and N: (3.5 points)
Then convert the table representation to a digraph representation as follows. Fill out the blanks in the following digraph. (1.5 points)
5. However, we don’t need the portion circled in the above digraph representation of the DFA (why?). By removing that portion, the DFA is like the one shown on the left side of the following figure. No points for this part.
By constructing production rules from this FA, we get the production set of the regular grammar on the right side of the above figure. Fill out the blanks in the above figure. (3 points)
· Solutions must be typed (word processed) and submitted to Canvas both as a pdf file and a word docx file before 23:59 on 9/24/2022. Don’t forget to name your files as
CS375_2022f_HW4-1_LastName.docx / CS375_2022f_HW4-1_LastName.pdf
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com