Homework 2
Last updated: Thu, 11 Feb 2021 11:18:05 -0500
Out: Wed Feb 3, 00:00 EST Due: Sun Feb 14, 23:59 EST
This assignment continues exploring deterministic finite automata (DFAs) using code.
Homework Problems
Simulating Computation for DFAs (3 points)
DFAs and the Language They Recognize (3 points)
DFA->XML (2 points)
The Union Operation (3 points)
README (1 point)
The Intersection Operation (Optional Bonus) (3 points)
Total: 12 points (+ 3 bonus points)
Submitting
Submit your solution to this assignment in Gradescope hw2.
- a Makefile with the following targets:
setup (optional)
run-hw2-dfa
run-hw2-dfalang
run-hw2-dfa2xml
run-hw2-union
run-hw2-intersection (optional)
a README containing the required information,
and, files containing the solution to each problem.
1 Simulating Computation for DFAs
Recall the formal definition of computation from page 40 of the textbook:
A finite automata M = (Q,\Sigma,\delta,q_0,F) accepts a string w = w_1,\ldots,w_n, where each character w_i \in \Sigma, if there exists a sequence of states r_0,\ldots,r_n, where r_i \in Q, and:
r_0=q_0
\delta(r_i,w_{i+1}) = r_{i+1}, for i = 0,\ldots,n-1
r_n\in F
This problem asks you to demonstrate, with code, that you understand this concept.
Your Tasks
Write a "run" predicate (a function or method that returns true or false) that takes two arguments, an instance of your DFA representation (as defined in A Data Representation for DFAs) and a string, and "runs" the string on the DFA.
The function should return true if the DFA accepts the string, and false otherwise.
Then write a program that reads from stdin and feeds that input, along with the Figure 1.4’s DFA (i.e., the one created in A First DFA) to your "run" predicate. This program writes accept to stdout if the DFA accepts the input and reject otherwise.
Your solution will be tested as follows:
Makefile target name: run-hw2-dfa
Input (from stdin): a (randomly generated) string in alphabet \Sigma = \{0,1\}
- Expected Output (to stdout):
accept, if Figure 1.4’s DFA accepts input,
otherwise reject otherwise
Example:
printf "000111" | make -sf Makefile run-hw2-dfa
Output: accept
printf "10" | make -sf Makefile run-hw2-dfa
Output: reject
2 DFAs and the Language They Recognize
The language that a DFA recognizes is the set of all strings accepted by the DFA.
Your Tasks
Write a function or method that, given an XML file containing an automaton element, constructs an instance of the DFA representation from A Data Representation for DFAs. You’ve already done part of this in Homework 0, which extracted the states, so now just extract the transitions.
Using your predicate from Simulating Computation for DFAs, write a function or method that, given a DFA, prints all strings in the language that it recognizes, up to strings of length 5, one per line.
You may find your solution to the Sets and Alphabets problem useful here.
Your solution will be tested as follows:
Makefile target name: run-hw2-dfalang
Input (from stdin): XML file name, containing a DFA automaton element
Expected Output (to stdout): all strings in the language of the DFA, up to strings of length 5, one string per line (order doesn’t matter, since we’re printing a set)
Example:
You can test your program with this file named fig1.4.jff containing the DFA from figure 1.4 of the textbook.
printf "fig1.4.jff" | make -sf Makefile run-hw2-dfalang
Output:00001
00011
00100
00101
00111
01001
01011
01100
01101
01111
10000
10001
10011
10100
10101
10111
11001
11011
11100
11101
11111
0001
0011
0100
0101
0111
1001
1011
1100
1101
1111
001
011
100
101
111
01
11
1
Example2:You can test your program with this file named dfa-empty.jff containing a DFA that only accepts the empty string.
printf "dfa-empty.jff" | make -sf Makefile run-hw2-dfa
Output:(it’s an empty line)
3 DFA->XML
Your Tasks
Write a function that converts an instance of your DFA to an XML string corresponding to an automaton element.
Implement the "three 1’s" DFA from class as an instance of your DFA representation.
Write a program that when run, calls your DFA->XML function with this DFA as argument, and prints the result to stdout.
Your solution will be tested as follows:
Makefile target name: run-hw2-dfa2xml
Input (from stdin): none
Expected Output (to stdout): XML representing the "three 1s" DFA from class
<state id="q1" name="q1"><initial/></state> |
<state id="q1" name="q1"> |
<initial/> |
</state> |
4 The Union Operation
This question will ask you to demonstrate, with code, that you understand the proof showing that the union operation is closed for regular languages (Theorem 1.25).
To do so, you will have to put together everything you’ve done so far in the homeworks.
Your Task
Implement a union operation for your DFAs. Specifically, write a function that, given:
a DFA recognizing language A_1, and
a DFA recognizing language A_2
This solution implements the algorithm from Theorem 1.25 of the textbook (so rereading that will be helpful), thus proving it.
Your solution will be tested as follows:
Makefile target name: run-hw2-union
Input (from stdin): the names of two XML files, separated by a space, each containing an automaton element representing a DFA
Expected Output (to stdout): an automaton XML string representing a DFA that is the union of the two inputs
Example:
You can test your program with these files:printf "dfa-a.xml dfa-b.xml" | make -sf Makefile run-hw2-union
Output:<automaton>
<state id="(1 1)" name="(1 1)"><initial/></state>
<state id="(1 2)" name="(1 2)"><final/></state>
<state id="(1 3)" name="(1 3)"></state>
<state id="(2 1)" name="(2 1)"><final/></state>
<state id="(2 2)" name="(2 2)"><final/></state>
<state id="(2 3)" name="(2 3)"><final/></state>
<state id="(3 1)" name="(3 1)"></state>
<state id="(3 2)" name="(3 2)"><final/></state>
<state id="(3 3)" name="(3 3)"></state>
<transition><from>(1 1)</from><to>(2 3)</to><read>a</read></transition>
<transition><from>(1 1)</from><to>(3 2)</to><read>b</read></transition>
<transition><from>(1 2)</from><to>(2 3)</to><read>a</read></transition>
<transition><from>(1 2)</from><to>(3 3)</to><read>b</read></transition>
<transition><from>(1 3)</from><to>(2 3)</to><read>a</read></transition>
<transition><from>(1 3)</from><to>(3 3)</to><read>b</read></transition>
<transition><from>(2 1)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(2 1)</from><to>(3 2)</to><read>b</read></transition>
<transition><from>(2 2)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(2 2)</from><to>(3 3)</to><read>b</read></transition>
<transition><from>(2 3)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(2 3)</from><to>(3 3)</to><read>b</read></transition>
<transition><from>(3 1)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(3 1)</from><to>(3 2)</to><read>b</read></transition>
<transition><from>(3 2)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(3 2)</from><to>(3 3)</to><read>b</read></transition>
<transition><from>(3 3)</from><to>(3 3)</to><read>a</read></transition>
<transition><from>(3 3)</from><to>(3 3)</to><read>b</read></transition>
</automaton>
5 The Intersection Operation (Optional Bonus)
Your Task
Implement intersection for your DFAs. Specifically, write a function that, given:
a DFA recognizing language A_1, and
a DFA recognizing language A_2
This is almost the same as union implemented in The Union Operation. See footnote 3 in the proof of Theorem 1.25 for how to implement intersection.
Then, create a "password checking" machine PW that recognizes the intersection of the following languages, i.e., A_1 \cap A_2 \cap A_3 \cap A_4.
You may assume the alphabet \Sigma = {A,B,C,a,b,c,1,2,3,!}.
A_1 = \{w \mid \textrm{length of } w \textrm{ is at least } 3\}
A_2 = \{w \mid w \textrm{ contains an uppercase letter}\}
A_3 = \{w \mid w \textrm{ contains a number}\}
A_4 = \{w \mid w \textrm{ contains a non-alphanumeric symbol}\}
Your solution will be tested as follows:
Makefile target name: run-hw2-intersection
Input (from stdin): An arbitrary string with chars in alphabet \Sigma
Expected Output (to stdout): valid if PW accepts the input, invalid otherwise.
Examples:
printf "abc" | make -sf Makefile run-hw2-intersection
Output: invalid
printf "abc1" | make -sf Makefile run-hw2-intersection
Output: invalid
printf "Abc1!" | make -sf Makefile run-hw2-intersection
Output: valid
Note: As usual, the submitted solution must actually construct four DFAs and then intersect them together.