Question 1. In the following we use the assumption that the number of different atoms on earth is finite. Furthermore, we say that any possible composition of a finitely many atoms is called a molecule. Note that a molecule can have several occurrences of the same atom. We say two molecules are equivalent if both the sets atoms and the number of occurrences of each of those atoms of the respective molecules are equal. Finally, the molecule universe is defined as the set of all possible molecules. a) Is the molecule universe countable? Provide a proof that shows correctness of your answer. A molecule group is a finite or infinitely large collection of different molecules from the molecule universe. b) Is the set of all molecule groups countable? Provide a proof that shows correctness of your answer. Question 2. Let Σ = {a,b,c}. Let L = { w ∈ Σ | w = s1s2 … sk for k ≧ 0 and si = xiyi where each xi consists of any number of a’s (that is zero or more), and each yi consists of either the empty string or: bb followed by any number of repetitions of symbol c (that is zero or more)} a) Prove that L is regular by designing a NFA N that satisfies the following constraints: N = (Q, Σ, �, q0, F) with |Q| = 3 (that is N has exactly three states), Σ = {a,b,c}, F = {q0}. Use a state diagram to show �. b) Give a DFA D with L(D) = L(N) = L. To build D, follow exactly the algorithm of the DFA design in the proof of the theorem “For every NFA there exists an equivalent DFA” discussed in class. Show your steps. Give the transition table to describe D’s transition function. c) How many states of DFA D from your answer in b) can be removed from D without changing its language? Question 3. a) Give a sequence of states for automaton N from Question 2.a) above, and string w = aaabbc that causes N to accept w. b) Give a sequence of states for N that does not cause N to accept w. c) Is w ∈ L(N)?
