# 2014 Qualifying Examination, Computational Theory, 100 points

 2014 Qualifying Examination, Computational Theory, 100 points (10 points for each problem) L is a regular language and decidable by a Deterministic Finite Automata (DFA). L1 is a language, which is defined by: . Prove that L1 is a regular language too. (Hint: Construct a DFA to decide L1.) Prove that the following language is NOT regular by using the Pumping Lemma of regular language: Prove that the following language is NOT regular by using MyHill-Nerode Theorem: Design a Pushdown Automata (PDA) to accept the following language: Please explain your Push Down Automata step by step. Is your deterministic? Verify your answer, please. Write down the context free grammar for the language of Problem 4. Can this language be generated by an un-ambiguous context free grammar? Prove that the following language is not context free by using the Pumping Theorem of Context Free Language: Design a Turing Machine (TM) to decide the following language by using machine schema: Is the TM a Linear Bounded Automata (LBA)? Justify your answer by counting the size of memory cells used in your algorithm. M is a Turing Machine which semidecides a language L1. Prove that the following problem is undecidable: Given a string , is (Hint: Using problem reduction. The candidate problem is the “equivalence of TM” problem.) Prove that the following problem is in the EXP class: M is a non-deterministic Turing machine and always halt in polynomial time. Given a string w, will M halt on w? It is known that the Hamilton path problem is NP-complete. (Given a graph G, is there a path which passes each vertex of G exactly once?) Prove that the following problem is NP-hard: Given a weighted graph Gw, is there a Hamilton path in Gw so that the path length ≤ K? (Assume all edge weights > 0 and K is a positive number.)