L is a regular language and decidable by a Deterministic Finite Automata (DFA). L_{1}is a language, which is defined by:. Prove that L_{1} is a regular language too. (Hint: Construct a DFA to decide L_{1}.)

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 L_{1}. 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 G_{w}, is there a Hamilton path in G_{w} so that the path length ≤ K? (Assume all edge weights > 0 and K is a positive number.)