Automata Theory homework

Q 01Proof by induction: we have a sequence of graphs where has spanning cycle, therefore base of induction is complete. Assume that for some , all graphs up to (including ) also have a spanning cycle. We need to show that in such a case would also have a spanning cycle. Indeed, suppose there are vertices in and we can numerate them in the same order as they appear in the spanning cycle of :Graph is constructed form by adding vertex which is connected to strictly more than a half of vertices of . This implies that by Dirichlet’s principle at least one of two conditions below must be true (without loss of generality we can further assume that it is the first condition):Or in other words must be connected to the two vertices that appear in the spanning cycle of on the consequent positions. Therefore, can plug into the spanning cycle between these vertices:It is obvious that the cycle above is a spanning cycle for . Q. E. D.Q 02The DFA should have five states which will correspond to the five possible remainders of division by 5. We will denote these states as with remainders corresponding to the index of each state and being the only acceptance state DFA will read each consequent symbol and switch to the next state according to the simple rule:The transition table for such DFA is the following:01The corresponding DFA is the following:Q 03In this task the DFA should search for the 01 substring in the first four bits that it reads. If it does not find such substring it should switch to the dead-end state which is non-acceptable. However, if 01 substring is found in the first four bits machine switches to the first acceptable state . From this state DFA checks next two bits (still staying in the acceptable states) and switching to the dead-end state if after the third bit no 01 substring is found. The proposed DFA is shown below: Q 04According to the definition the fact that is a regular language implies that there exists a DFA that recognizes . Therefore, to show that is regular we can show that NFA that recognizes can be constructed and due to the equivalence of DFA’s and NFA’s it will imply that DFA for also exists and such language is regular.Suppose that some DFA M recognizes . This implies that after reading any word (here ) M finishes working in some acceptable state . Moreover, upon reading only M was in some state from which was accessible. By adding new acceptable state , making it the only acceptable and creating an ε-transition from to we will get NFA that will recognize x. By taking other y’ from and other possible x’y’ from we may need to add the new ε-transition from some other …