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.
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.)