On this page:
1 Simulating Computation for DFAs
2 DFAs and the Language They Recognize
3 DFA->XML
4 The Union Operation
5 The Intersection Operation (Optional Bonus)

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

  1. Simulating Computation for DFAs (3 points)

  2. DFAs and the Language They Recognize (3 points)

  3. DFA->XML (2 points)

  4. The Union Operation (3 points)

  5. README (1 point)

  6. The Intersection Operation (Optional Bonus) (3 points)

Total: 12 points (+ 3 bonus points)

Submitting

Submit your solution to this assignment in Gradescope hw2.

A submission must include the following files (NOTE: everything is case-sensitive):
  • 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:

  1. r_0=q_0

  2. \delta(r_i,w_{i+1}) = r_{i+1}, for i = 0,\ldots,n-1

  3. r_n\in F

This problem asks you to demonstrate, with code, that you understand this concept.

Your Tasks

  1. 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.

  2. 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

Your solution will be tested as follows:

3 DFA->XML

Your Tasks

Your solution will be tested as follows:

Note: Whitespace doesn’t matter for XML. So something like:

    <state id="q1" name="q1"><initial/></state>

is equivalent to:

    <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

returns a DFA recognizing A_1 \cup 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:

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

returns a DFA recognizing A_1 \cap 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,!}.

Your solution will be tested as follows:

Note: As usual, the submitted solution must actually construct four DFAs and then intersect them together.