Unless otherwise stated, each question requires sufficient justification to convince the reader of the correctness of your answer.

For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions.

We strongly encourage you to typeset your solutions in LATEX.

If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up.

0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).

1. We say that a DFA decides  a language L (a set of binary strings) if it accepts every string in L (i.e., returns “yes”) and rejects every string not in L (i.e., returns “no”).  Intuitively, this means that it solves the decision problem associated with L.  The goal of this question is to draw DFAs that decide various simple languages. If you’re using LATEX, you might find https://www.cs.unc.edu/∼otternes/comp455/fsm designer/ useful.

No justification is required for parts (a)- (c).

(a) Draw a DFA that decides the language of strings that match the pattern 0(11) ∗ 0, i.e.,

strings that begin and end with the character 0, with zero or more copies of 11 in between.

(b) Draw a DFA that decides the language of strings that end with 1.

(c) Draw a DFA that decides the language of strings that match the pattern 01 ∗ or  the pattern 110∗ , i.e., the string either (i) starts with 0 and then has zero or more 1s (and nothing more), or (ii) starts with 11 and then has zero or more 0s (and nothing more). Hint : Your answer should have less than 6 states.

(d) What language is decided by the following DFA? Briefly explain your reasoning.

2. Analogously, we say that a Turing machine decides a language L if it accepts every string in L and rejects every string not in L.  In contrast to DFAs, since a Turing machine may run indefinitely, it is not necessarily the case that every Turing machine decides a language.

(a) State what language, if any, the following Turing machine decides. If it does not decide

any language, then give an input on which the Turing machine runs indefinitely, and give the set of inputs that the Turing machine accepts. In either case, briefly justify all your responses, and provide a high-level description of what the Turing machine does.

(b) Give the state machine diagram for a Turing machine that decides the language L = {0j1k  : j < k},

which consists of binary strings that contain j 0’s followed by k 1’s, for some non-negative integers 0 ≤ j < k . Briefly describe its design and justify its correctness.

Hint: Modify the machine from lecture that decides L = {0k 1k  : k ≥ 0}.