Shai Simonson         CS 301         Languages and Automata

Assignment 1 (40 points)


Due:  Friday, February 7

1.  DFAs  (9 points)

Draw Deterministic Finite Automata to accept the following sets of strings over the alphabet {0,1}:

       a. All strings that contain exactly 4 "0"s.
       b. All strings ending in "1101".
       c. All strings containing exactly 4 "0"s and at least 2 "1"s.
       d. All strings whose binary interpretation is divisible by 5.
       e. All strings that contain the substring 0101.
       f.  All strings that start with 0 and have odd length or start with 1 and have even length.
       g. All strings that don’t contain the substring 110.
       h. All strings of length at most five.
       i.  All strings where every odd position is a 1.

   2.  NFAs   (6 points)

     Draw Non-deterministic Finite Automata with the specified number of states to accept the following sets:

       a. All strings containing exactly 4 "0"s or an even number of "1"s. (8 states)
       b. All strings such that the third symbol from the right end is a "0". (4 states)
       c. All strings such that some two zeros are separated by a string whose length is 4i for some i >= 0. (6 states)
       d. All strings that contain the substring 0101. (5 states)
       e. All strings that contain an even number of zeros or exactly two ones. (6 states)
       f. The language 0*1*0*0. (3 states)

   3. Converting NFAs to DFAs  (4 points)

       a.  Convert the NFA in 2f into a Deterministic Automaton.
       b.  Convert the NFAs on pages 31-32  in text:  8, 12.

   4. Discrete Math Review – Proofs  (2 points)

     Analyze the two languages below. They are two descriptions of the same language – strings of balanced parentheses.

     Language 1: The set of strings where each string w has an equal number of zeros and ones; and any prefix of w has at least as many zeros as
     ones.
     Language 2: The set of strings defined inductively as follows: if w is in the set then 0w1 is also in the set; if u and v are in the set then so is uv; and
     the empty string is in the set.

       a.  Prove that every string in Language 2 is contained in Language 1. (Hint:  a proof by induction is easiest, because Language 2 is defined inductively).
       b.  Extra Credit: Prove they are equal (i.e., Language 1 is also contained in Language 2).

   5. Closure Problems  (5 points)

     You may use examples to illustrate your proofs. Note a proper prefix is any prefix that is not the empty string or the whole string itself. Also, note that regular sets are not closed under subset
     That is, subsets of regular sets are not necessarily regular.  Indeed, a subset is often more difficult to recognize than the original.

       a. Prove that if L1 is regular and L2 is regular then so is L1-L2 (the set of all strings in L1 but not in L2).
       b. Prove that if L is regular then Prefix(L) is regular. Prefix(L) is the set of all strings which are a proper prefix of a string in L.
       c. Prove that Regular Sets are closed under MIN. MIN(R), where R is a regular set, is the set of all strings w in R where every proper prefix of
         w is in not in R. (Note that this is not simply the complement of Prefix).
       d. Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).
       e. What about infinite intersection? Hint: Use DeMorgan's Law
       f. Extra Credit:  Prove that if L is regular so is Half(L). Half(L) is the set of all first halves of strings in L.

   6. Regular Expressions  (5 points)

     Write regular expressions for each of the following languages over the alphabet {0,1}. Provide justification that your regular expression is correct.

       a. The set of all strings in which every pair of adjacent zeros appears before any pair of adjacent ones.
       b. The set of all strings not containing 101 as a substring.
       c. The set of all strings with at most one pair of consecutive zeros and at most one pair of consecutive ones.

   7. Converting Finite Automata to Regular Expressions (1 point)

       Page 28.  Convert Example 3.9 to a regular expression.  Show your work.

   8. Regular Expression Identities  (3 points)

     Prove (give at least a few words of justification), or disprove (by counterexample) that each pair of regular expressions represent the same
     language. Assume that r, s and t represent regular expressions over the alphabet {0,1}.

       a. r(s + t) and rs + rt
       b. (r*)*and r*
       c. (r + s)* and r*s*

   9. Final States  (2 points)

       a. Explain why every NFA can be converted to an equivalent one that has a single final state.
       b. Give a counterexample to show that this is not true for DFA’s.
       c. Extra Credit:  Describe the languages that are generated from a DFA with just one final state.

  10. Miscellaneous Problems (3 points)

       a. Draw the minimum deterministic finite state machine to accept the following regular expression and succinctly describe the set in English.
         [00 + 11 + (01 + 10)(00 + 11)*(01 + 10)]*   (Hint:  The minimum size of the machine is 4 states).

       b. Show that the following is a regular language:     The strings that contain an equal number of occurrences of the substrings 01 and 10.
 

back


shai@stonehill.edu

http://www.stonehill.edu/compsci/shai.htm