A R S D I G I T A   V N I V E R S I T Y
Month 8: Theory of Computation
Problem Set 1 - Prof. Shai Simonson
1. DFAs

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

1. All strings that contain exactly 4 "0"s.
2. All strings ending in "1101".
3. All strings containing exactly 4 "0"s and at least 2 "1"s.
4. All strings whose binary interpretation is divisible by 5.
5. (1.4c) All strings that contain the substring 0101.
7. (1.4f) All strings that don’t contain the substring 110.
8. (1.4g) All strings of length at most five.
9. (1.4i) All strings where every odd position is a 1.

2. NFAs

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

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

3. Converting NFAs to DFAs

1. Convert the NFA in 2f into a Deterministic Automaton.
2. 1.12a in the text.
3. 1.12b in the text.

4. Discrete Math Review – Proofs

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.

1. Prove that every string in Language 2 is contained in Language 1.
2. Extra Credit: Prove they are equal (i.e. Language 1 is also contained in Language 2).

5. Closure Problems

You may use examples to illustrate your proofs.

1. 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).
2. 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.
3. 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).
4. Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).
6. Extra Credit: (1.42) 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

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

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

7. Converting Finite Automata to Regular Expressions

1. 1.16a in the text.
2. 1.16b in the text.

8. Regular Expression Identities

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

1. r(s + t) and rs + rt
2. (r*)*and r*
3. (r + s)* and r*s*

9. Final States

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

10. Optional Extra Problems

1. Draw a Finite Automaton to accept the following regular expression and succinctly describe the set in English.
[00 + 11 + (01 + 10)(00 + 11)*(01 + 10)]*
2. The language of addition: 1.25 in the text.
3. Show that the following is a regular language:
(1.41) The strings that contain an equal number of occurrences of the substrings 01 and 10