Homework 1

15-212 Java Spring 98

21 January 1998

Instructors:  Mosur and Tygar

Due at start of your section on 28 January.  No late assignments accepted.   No collaboration or consulting other students -- this will be considered cheating. Please be extremely neat and concise in writing up your answers.  Answers that are not clear to the grader, are difficult to read or understand, or are too long, will receive no credit.

For the exercise below, suppose that the alphabet consists of the set of ASCII characters.  Furthermore, in the FSA diagrams you draw, you may use the notations all and all else to indicate state transitions; the notation all indicates that any input character will cause the given state transition from the given state; the notation all else indicates that if no other state transition is permitted on a given input character from a given, then the all else transition should be taken.

  1. Give a DFSA that accepts exactly those strings that have the substring cat.   Examples of strings that we would accept include sophisticate or publication but not bureaucrat.
  2. Give a compact NFSA that accepts exactly those strings that have the substring anaan.   So we would accept strings such as canaan.  Test your NFSA on the string ananaan.
  3. Convert your NFSA in part (2) to a compact DFSA.  Again, test your DFSA on the string ananaan.
  4. Write regular expressions for the languages accepted by your machines in parts (1) and (3).
  5. Suppose we wanted to add a function to a text editor that would search for a substring in text.  The "obvious" way to do this would be to search the text for all occurences of the first character, and then, for each match, see if the second character matched, and then the third, and so on.  Show how this may result in the editor having to read some characters multiple times, so that the time required can be longer than the file length.
  6. Describe, for a specific substring, how to automatically build a specific FSA matched for that substring.  What is tricky about substrings such as anaan?   Extrapolate from parts (1) and (3) to describe how to build such a facility that only needs to read each character in the file only once -- thus making the program more efficient than in part (5).
  7. Do exercise 2.2.10 in Lewis and Papadimitrou.
  8. Do exercise 2.4.4 in Lewis and Papadimitrou.