Month 8: Theory of Computation

Problem Set 1 - Prof. Shai Simonson

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

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

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

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

- Converting NFAs to DFAs
- Convert the NFA in 2f into a Deterministic Automaton.
- 1.12a in the text.
- 1.12b in the text.

- 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.- Prove that every string in Language 2 is contained in Language 1.
- Extra Credit: Prove they are equal (i.e. Language 1 is also contained in Language 2).

- Closure Problems
You may use examples to illustrate your proofs.

- 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).
- 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.
- 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).
- Prove that Regular Sets are NOT closed under infinite union. (A counterexample suffices).
- What about infinite intersection?
- 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.

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

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

- Converting Finite Automata to Regular Expressions
- 1.16a in the text.
- 1.16b in the text.

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

- r(s + t) and rs + rt
- (r*)*and r*
- (r + s)* and r*s*

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

- Optional Extra Problems
- 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)]* - The language of addition: 1.25 in the text.
- 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

- Draw a Finite Automaton to accept the following regular expression and succinctly describe the set in English.