3

Let $S_n$ be as given and let $S$ be a subset of $S_n$. We will show that the following algorithm gives us $S$. for $i$ going from $n-1$ to $0$ $\\\\\ \ \ \ \text{Add}(S_n)$ $\\\\\ \ \ \ \text{if }i\not\in (S)\ \text{RemoveZero}(S_n)$ We go through the loop $n$ times. If an element $k$ doesn't get removed then its final value is $k+n\ \text{mod}\ n=k$ ...


2

Imagine you are sitting at a circular table with $n$ place settings, each of which has a cupcake (numbered $0$ to $n-1$). You can perform one of these two actions as many times as you like: Eat the cupcake in front of you. Rotate the table one spot clockwise. Do you see how, for any subset $S$ of cupcakes, it is possible to eat all of the cupcakes outside ...


2

Hint. If $A$ is the alphabet, $(AA)^*$ is the set of words of even length. Now, what is $A^*A^*$?


1

Both automata start from a single starting state. A deterministic automaton, if it is in some state $q$ and it reads an input character, it will transit to a single state $q'$. A non-deterministic automaton can transit from a state $q$ to many states $q_1, q_2, \ldots, q_k$ at the same time by reading a single input character. Also, a non-deterministic ...


Only top voted, non community-wiki answers of a minimum length are eligible