COMP2022/2922: Models of Computation - Assignment 2: Automation
comp2022/2922 Assignment 2 (80 marks) s2 2022
Problem 1. (10 marks, 5 marks each)
Let Σ = {a, b}. For each of the following languages, provide a nondeterministic finite automaton for that language. No justification is necessary. For full marks, your automaton should use at most the specified number of states. Partial marks will be awarded for larger automata.
1. The set of strings with the property that there are two occurrences of the same letter that are exactly 3 positions apart (i.e. there are exactly 2 letters between them). For example, abaaa ∈ L, ababa ∈/ L. (8 states)
2. The set of strings whose length is not divisible by 6 or that contain at least two bs (or both). For example, ab, ababab ∈ L, ε, aabaaa ∈/ L. (8 states)
Problem 2. (20 marks, 10 marks each)
Let Σ = {a, b}. For each of the following languages, prove that the language is
not regular.
3. The set {a2nbn : n ≥ 1}.
4. The set of strings {y0,y1,y2,···} where y0 = ε, yi = yi−1ai if i is an odd positive integer, and yi = yi−1bi if i is an even positive integer. For example, y0 = ε,y1 = a,y2 = abb,y3 = abbaaa,y4 = abbaaabbbb, etc.
Problem 3. (20 marks, 5/5/10)
Let Σ = {a,b}. For each of the following languages, provide a deterministic Turing Machine that decides that language. No justification is necessary. For full marks, your machines should work for any input and be reasonably efficient. Guidelines on this efficiency will be posted on Ed.
1. The language {anbn+1 : n ≥ 0}.
2. The language from Problem 2, part 2.
3. The set of strings of the form uxu, where u, x ∈ Σ∗ are strings and u ̸= ε. For example, bb, abbba, abbab, baaaaaababaa, abbababbab ∈ L while ε, b, ba, aaabab, bbabaabbaa ∈/ L.
Problem 4. (30 marks) An implicit string is a way of writing a string where we allow the use of exponents. For example, (abc)3b is an implicit string that equals abcabcabcb. Implicit strings allow us to write very long strings much more concisely, such as
(abc)10000000000000000000000000000000000db
which is too large to store in a modern computer’s memory but can be written in under 100 characters as an implicit string. An implicit string is given in the form
(x1) 1(x2) 2 ...(xk) k
where x1, x2, . . . , xk are (ordinary) strings and n1, n2, . . . , nk are positive integers.
Your task is to write code that takes an automaton N and a sequence of implicit strings from stdin, and outputs whether N accepts each of the strings to stdout. Some skeleton code will be provided (in Python) that demonstrates how to handle the input/output. You may assume that the input is valid. Your program will not be tested on invalid input.
You are guaranteed that all input automata will have fewer than 100 states, all input implicit strings will have k < 10, and that all resulting strings will be of length less than 2
In each subproblem, 50% of the marks will be for DFA cases and 50% will be for NFA cases.
Here is an explanation of the restrictions:
- ”small string” means that the resulting string will be of length at most 1000
- ”1 symbol” means that the implicit string will be the exponent of a single symbol
- ”1 string” means that the implicit string will be the exponent of a single string
- ”powers of 2” means that all exponents will be powers of 2. The given ex- ample values are 250 = 1125899906842624 and 253 = 9007199254740992. You may find the Python function math.log(x,2) useful in determining which power of 2 a number is.
Hints:
- For the small string test cases, it will be sufficient to expand out the implicit string and run the automata on it.
- For the NFA cases, it is not recommended to convert the NFA to a DFA, because this can cause an exponential blowup in automata size. You should find a way to decide membership for NFAs while avoiding this exponential blowup.
- For the large string test cases, expanding out the implicit string will not be sufficient, because this causes an exponential blowup in string length. You will need to find a more efficient way to run the automaton on the im- plicit string. Think about what happens when the automaton reads a single character, what happens when it reads multiple characters in sequence, and what happens when it reads the same sequence twice. Furthermore, think about working with the entire transition function, rather than just the tran- sition that actually gets taken.
- Although the general problem (i.e., subproblem 5) is quite difficult, the first few subproblems are easier, so you should attempt them to earn partial marks even if you cannot solve the general problem. The subproblems are in rough difficulty order, so it is recommended that you gradually extend your solution to handle subsequent subproblems and/or to handle NFAs for a subproblem.
- The restriction to powers of 2 provides a hint on how to handle the general problem. Remember that if n = 2i, then for a string x we have that xn =
(x2)2...2 with i squarings.
