Description

Problem 1 (5 points) answer the following questions:
a) If has elements and has elements, how many elements are in x?
• There are × elements in x
= {1, 2, 3} Assume elements in
= {, , } Assume elements in
|| = a = 3 The length of is 3, therefore a = 3
|| = b = 3 The length of is 3, therefore b = 3
x = {(1, ),(1, ), (1, ), (2, ), (2, ), (2,), (3, ), (3, ), (3, )}
|x| = 9 Listing the elements shows the length of x is 9
× = 3 × 3 = 9 Calculating × also shows a length of 9
b) If is a set with elements, how many elements are in the power set of ?
• The power set is of 2
= {0,1} Assume elements in
|| = c = 2 The length of is 2, therefore = 2
() = {∅ , 0,1, (0,1)}
|()| = 4 Listing the elements shows the length of () is 4
2 = 22 = 4 Calculating 2 also shows a length of 4
c) Let = {(1, 2), (2, 3), (2, 4)} is a relation on the set {1,2, 3, 4}. What is ∗ (Reflexive and transitive closure)?
• ∗ = {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 3), (2,4), (3, 3), (4, 4)}
= {(1,2), (2, 3), (2,4)} Elements in
Find Reflexive Closure of :
= ∪ {(, ) | ∈ } Reflexive Closure Formula
= {(1,2), (2, 3), (2, 4)} ∪ {(1,1), (2, 2), (3,3), (4,4)} Subtitute Values
= {(1,1), (1, 2), (2, 2),(2, 3), (2, 4), (3, 3), (4, 4)} Combine Elements (Union) Find Transitive Closure of :
⇒ (, ) Transitive Property
(, ) (, ) (, )

(1, 2) (2, 3) (1, 3)
(1, 4)

(1, 2) (2, 4)
(1, 3)
(2, 3) (3, 1)
(3, 2)
(3, 3)
(3, 4)
(1, 4)
(2, 4)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(1, 1)
(2, 1)
(3, 1)
(4, 1) (1, 2)
(1, 3)
(1, 4)

+ = {(1,2), (1, 3), (1, 4), (2, 3), (2, 4)} Include Transitive Pairs
Find Missing Pairs

Find Reflexive and Transitive Closure of :
Reflexive and Transitive Closure Formula
Subtitute Values

Combine Elements
Problem 2 (5 points) Answer the following questions about the state diagrams of a DFA (1)

a) What is the start state?
• 1
b) What is the set of accept states?
• {2}
c) What sequence of states does the machine go through on input ?
• {1,2,3,1,1}
d) Does the machine accept the string ?
• No, because string finishes in 1, which is not an accept state.
e) Does the machine accept the string ?
• No, because string finishes in 1, which is not an accept state.
Problem 3 (10 points) Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts, = (, ).
a) {| has at least three ’ and at least two ’} • 1 = {| has at least three ’}

Figure 1: DFA with Test Input
• 2 = {| has at least two ′}

Figure 2: DFA with Test Input
• {| has at least three ’ and at least two ′}
The Transition Function

STATE INPUT A B TRANSITION
= (1,2) 1(1,) 2(2,) (, )
0, 0 1(0,) = 1 2(0,) = 0 ,
0, 0 1(0,) = 0 2(0,) = 1 ,
1,0 1(1,) = 2 2(0,) = 1 ,
1,0 1(1,) = 1 2(0,) = 1 ,
2, 0 1(2,) = 3 2(0,) = 0 ,
2, 0 1(2,) = 2 2(0,) = 1 ,
3, 0 1(3,) = 3 2(0,) = 0 ,
3, 0 1(3,) = 3 2(0,) = 1 ,
0, 1 1(0,) = 1 2(1,) = 1 ,
0, 1 1(0,) = 0 2(1,) = 2 ,
1,1 1(1,) = 2 2(1,) = 1 ,
1,1 1(1,) = 1 2(1,) = 2 ,
2, 1 1(2,) = 3 2(1,) = 1 ,
2, 1 1(2,) = 2 2(1,) = 2 ,
3, 1 1(3,) = 3 2(1,) = 1 ,
3, 1 1(3,) = 3 2(1,) = 2 ,
0, 2 1(0,) = 1 2(2,) = 2 ,
0, 2 1(0,) = 0 2(2,) = 2 ,
1,2 1(1,) = 2 2(2,) = 2 ,
1,2 1(1,) = 1 2(2,) = 2 ,
2, 2 1(2,) = 3 2(2,) = 2 ,
2, 2 1(2,) = 2 2(2,) = 2 ,
3, 2 1(3,) = 3 2(2,) = 2 ,
3, 2 1(3,) = 3 2(2,) = 2 ,

Figure 3: DFA with Test Input
b) {| has exactly two ’s and at least two ’} • 1 = {| has exactly two ’s}

Figure 4: DFA with Test Input
• 2 = {| has at least two ’}

Figure 5: DFA with Test Input
• {| has exactly two ’s and at least two ’}
The Transition Function

STATE INPUT A B TRANSITION
= (1,2) 1(1,) 2(2,) (, )
0, 0 1(0,) = 1 2(0,) = 0 ,
0, 0 1(0,) = 0 2(0,) = 1 ,
1,0 1(1,) = 2 2(0,) = 1 ,
1,0 1(1,) = 1 2(0,) = 1 ,
2, 0 1(2,) = 3 2(0,) = 0 ,
2, 0 1(2,) = 2 2(0,) = 1 ,
3, 0 1(3,) = 3 2(0,) = 0 ,
3, 0 1(3,) = 3 2(0,) = 1 ,
0, 1 1(0,) = 1 2(1,) = 1 ,
0, 1 1(0,) = 0 2(1,) = 2 ,
1,1 1(1,) = 2 2(1,) = 1 ,
1,1 1(1,) = 1 2(1,) = 2 ,
2, 1 1(2,) = 3 2(1,) = 1 ,
2, 1 1(2,) = 2 2(1,) = 2 ,
3, 1 1(3,) = 3 2(1,) = 1 ,
3, 1 1(3,) = 3 2(1,) = 2 ,
0, 2 1(0,) = 1 2(2,) = 2 ,
0, 2 1(0,) = 0 2(2,) = 2 ,
1,2 1(1,) = 2 2(2,) = 2 ,
1,2 1(1,) = 1 2(2,) = 2 ,
2, 2 1(2,) = 3 2(2,) = 2 ,
2, 2 1(2,) = 2 2(2,) = 2 ,
3, 2 1(3,) = 3 2(2,) = 2 ,
3, 2 1(3,) = 3 2(2,) = 2 ,

Figure 6: DFA with Test Input
Problem 4 (10 points) 1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.
1. {| begins with a 1 and ends with a 0}

Figure 7: DFA with Test Input
2. {| begins with at least three 1s}

Figure 8: DFA with Test Input
Problem 5 (10 points) 1.7 Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.
a) The language {| ends with 00} with three states

Figure 9: NFA with Test Input
• Since NFAs accept input if any sequence of the possible choices leads to a final state, we can loop all 1’s and 0’s until the final two 0’s appear (aka we do not need to account for every possible appearance of a 1 since NFAs automatically considers that possibility)
Problem 6 (10 points) 1.16 Use the construction given in Theorem 1.39 to convert the following nondeterministic finite automata to equivalent deterministic finite automata (show the process).

1. Determine -closure for each state
-closure =self-state -reachable states -closure Formula self -reachable
{1} {1} {2} {1, 2}
{2}
{3}
{2}
{3} {2}
{3}
Name new state

2. Obtain ′ transition for any New States Found
• Calculate ′Transition for
= {1,2} State
′(, ) = -closure{(, )} ′Transition Formula
′ -closure Substitute Values
′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ Find -closure for each
′ Solve for ′
′ Name new state
′ -closure Substitute Values
′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ Solve for ′
• Calculate ′Transition for
= {1,2, 3} State
′ -closure Substitute Values ′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ Find -closure for each
′ Solve for ′
′ State B
′ -closure Substitute Values ′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ -closure Remove Empty Sets
′ Find -closure for each , Solve for ′
′ Name new state
• Calculate ′Transition for
= {2,3} State
′ -closure Substitute Values
′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ Find -closure for each
′ Solve for ′ ′ State A
′ -closure Substitute Values
′ -closure Expand, Showing Union
′ -closure Find Transition for each
′ -closure Remove Empty Sets
′ Find -closure for each , Solve for ′
′ State C
3. Determine Final State(s) for DFA
• Identify Final State in Original NFA

Figure 10: The Final State in the original NFA is 2
• Identify any DFA states which contain the NFA Final State DFA States
{1,}
{1,, 3}
{,3}
Figure 11: States A, B, C will be Final States in the DFA
❖ Converted DFA:

Figure 12: DFA with Test Input
By comparing the results of which strings are accepted/rejected, we can see that the DFA above is equivalent to the provided NFA:

Figure 13: Provided NFA with Test Input
Problem 7 (20 points) 1.18 Give regular expressions generating the following languages. In all parts the alphabet is {0, 1}
a) {| has at least one
•
b) {| starts and ends with same symbol}
•
c) {| ||
•
d) {| every 3rd position of is
•
e) {| has equal numbers of ‘01’ and ‘10’}
•
Problem 8 (10 points) 1.19 Use the procedure described in Lemma 1.55 to convert the following regular expressions to nondeterministic finite automata.
a)
•

• 1

•

•

• 000

• (0 ∪ 1)∗000

• (0 ∪ 1)∗000(0 ∪ 1)∗

Figure 14: -NFA of (0∪1)∗000(0∪1)∗
Additionally, I have converted this -NFA to NFA, as shown below

Figure 15: NFA of (0∪1)∗000(0∪1)∗
Problem 9 (20 points) A syntactically valid email address is made up of a username followed by ‘@’ followed by a list of at least two domain names separated by ‘.’. Assume that user and domain names are made up of letters [a-z] and digits [0-9], and the main domain name, i.e., the last domain name, contains two or three characters.
VALID INVALID
abc@dsu.edu a.b.ab
abc@pluto.dsu.edu ab@ab
11@123.com ab@ab.abcd
1. (5 points) Use JFLAP design a finite automaton to recognize valid mail address. Enclose your FA’s JFLAP file (.jff) in your homework submission.

Figure 16: -NFA for Email Address Strings

Figure 17: NFA for Email Address Strings

Figure 18: DFA for Email Address Strings
JFLAP .jff files are also attached in homework submission as HW1-Q9eNFA[Final].jff, HW1Q9DFA[Final].jff

2. (5 points) Test the above six testing cases using JFLAP Multiple Run function. You can include more testing cases if you want. Include a screenshot of your testing results in your homework submission as below:

Figure 19: Test Input for Email ε-NFA

Figure 20: Test Input for Email NFA

Figure 21: Test Input for Email DFA
3. (10 points) Use a programming language at your choice to implement the FA designed in Step 1. Submit your source code and also write a readme file to show how to compile your program, how to run your program, and some testing results you have. (Note: The program should implement the FA based on your design and simulate the way how FA works. There is no credit for the program if the implementation is based on the use of regular expressions.)
• Will be included in HW folder