Homework 1

Last updated: Tue, 22 Sep 2020 15:09:16 -0400

Out: Wed Sept 16, 00:00 EST Due: Tues Sept 22, 23:59 EST

This assignment involves exploring deterministic finite automata (DFAs) using code.

Homework Problems

1. A Data Representation for DFAs

2. A Regular Language

3. DFAs and the Language They Recognize

4. Create Your Own DFA

5. The Union Operation

6. The Intersection Operation (Optional Bonus)

Submitting

Submit your solution to this assignment in Gradescope hw1.

1 A Data Representation for DFAs

Since most of the course material on DFAs involves designing, running them, and proofs by construction, we will use programming as a nice way to get hands-on experience.

Your Tasks

1. Design a data representation for the DFAs from the textbook. You may use objects, structs, or anything else available in your language.

2. Implement your data representation in your chosen language.

3. Write a predicate (a function or method that returns true or false) that takes an input string and an instance of your DFA and "runs" it on the DFA. It should return true if the DFA accepts the input, and false otherwise.

(There won’t be any explicit tests for this problem, though you’ll need this implementation to do the rest of the homework.)

2 A Regular Language

Create an instance of your DFA recognizing the language:

A = \{w \mid \textrm{length of } w \textrm{ is at least } 3\}

You may assume it has alphabet \Sigma=\{0,1\}.

Recall that a language is regular if some finite automaton recognizes it.

Thus your solution proves that A is a regular language.

Your Task

Implement an instance of your DFA recognizing language A.

Your solution will be tested as follows:

• Input (from stdin): a string in alphabet \Sigma

• Expected Output (to stdout): accept if input is in A, reject otherwise

• Makefile target name: run-hw1-regular

• Example:

  printf "000111" | make -sf Makefile run-hw1-regular

  Output: accept

  printf "1" | make -sf Makefile run-hw1-regular

  Output: reject

3 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 (see Homework 0, Parsing XML Files), constructs an instance of your DFA.

• Using your predicate from above, 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:

• 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

• Makefile target name: run-hw1-dfa

• 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-hw1-dfa

  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 acceps the empty string.

  printf "dfa-empty.jff" | make -sf Makefile run-hw1-dfa

  Output:
  (it’s an empty line)

4 Create Your Own DFA

Your Tasks

• Write a function that converts an instance of your DFA to an XML string corresponding to an automaton element.

• Design and implement any a DFA of your choice. Write it to an XML file called dfa.xml using the DFA->XML function you just wrote.

  Any valid DFA in a correctly named file will receive credit.

5 The Union Operation

Your Task

Implement the union operation for your DFAs. Specifically, write a function that, given:

Your solution proves Theorem 1.25 from the book so rereading that will be helpful.

To do this, you’ll need to be able to extract individual components of a DFA instance, e.g., the states, transitions, etc., and use them to create a new DFA.

Your solution will be tested as follows:

• 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

• Makefile target name: run-hw1-union

• Example:

  You can test your program with these files:

  • dfa-a.xml: recognizes the language \{"a"\}

  • dfa-b.xml: recognizes the language \{"b"\}

  printf "dfa-a.xml dfa-b.xml" | make -sf Makefile run-hw1-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>

6 The Intersection Operation (Optional Bonus)

Your Task

Implement intersection for your DFAs. Specifically, write a function that, given:

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 P 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:

• Input (from stdin): An arbitrary string with chars in alphabet \Sigma

• Expected Output (to stdout): good if P accepts the input, bad otherwise.

  In addition, the filename for the source code must have the word intersect in it, e.g. hw1-intersection.py

• Makefile target name: run-hw1-intersection

• Examples:

  printf "abc" | make -sf Makefile run-hw1-intersection

  Output: bad

  printf "abc1" | make -sf Makefile run-hw1-intersection

  Output: bad

  printf "Abc1!" | make -sf Makefile run-hw1-intersection

  Output: good

7 More DFAs (Optional Bonus)

You may attempt this bonus problem only after completing the rest of the assignment.

Your Task

Use your HW1 solution to create another DFA.

Submit it as an automaton XML element in a file named extradfa1.xml.

It must be a new DFA you come up with. It cannot be a DFA that we have seen in class or homeworks. Slight tweaking of previously seen DFAs doesn’t count either.

If your DFA is interesting enough, it may be added to this homework’s test suite.

For this task, you may submit up to three DFAs. Each extra DFA you submit is worth 1 bonus point, for a maximum total of 3 bonus points.