comp2022/2922 Assignment 2 (80 marks) s2 2022
• This assignment is due in Week 7 on Wednesday 14 September, 11:59pm on Gradescope.
Copyright By PowCoder代写 加微信 powcoder
• All work must be done individually without consulting anyone else’s solutions in accor-
dance with the University’s “Academic Dishonesty and Plagiarism” policies.
• You will be evaluated not just on the correctness of your answers, but on your ability to
present your ideas clearly and logically. You should always explain how you arrived at
your answer unless explicitly asked not to do so. Your goal should be to convince the
person reading your work that your answers are correct and your methods are sound.
• For clarifications, input formats, and more details on all aspects of this assignment (e.g.,
level of justification expected, late penalties, repeated submissions, what to do if you are
stuck, etc.) you are expected to regularly monitor the Ed Forum post “Assignment FAQ”.
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.
1. The set {a2nbn : n ≥ 1}.
2. 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}.
https://sydney.edu.au/students/academic-dishonesty.html
https://edstem.org/au/courses/9602/discussion/950943
comp2022/2922 Assignment 2 (80 marks) s2 2022
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
n2 . . . (xk)
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 han-
dle 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 262.
Subproblem Restrictions Marks Example implicit string
1 small string 12 (ab)30(cda)200(bb)17
2 1 symbol, powers of 2 6 (a)1125899906842624
3 1 string, powers of 2 4 (abca)9007199254740992
4 powers of 2 4 (abc)1125899906842624(db)9007199254740992
5 no restrictions 4 (abc)1234567891234567(db)73
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
comp2022/2922 Assignment 2 (80 marks) s2 2022
• ”1 string” means that the implicit string will be the exponent of a single
• ”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.
• 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
• 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 =
with i squarings.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com