Formal Language & Automata Theory

The decision problem is the function from string to _____.

(i) char
(ii) int
(iii) boolean
(iv) None of the above

The Halting Problem is

(i) Decidable
(ii) Undecidable
(iii) Context-Free
(iv) Regular

Which of the following is used to prove many undecidability results?

(i) Pumping Lemma
(ii) Rice's Theorem
(iii) Chomsky Normal Form
(iv) Subset Construction

Explain the concept of Universal Turing Machine. How does it help in proving undecidability?

Write short notes on the following:
(i) Deterministic PDA vs. non-deterministic PDA
(ii) Universal Turing machine
(iii) Non-deterministic Turing machine
(iv) Post correspondence problem (PCP)

Write a short note on: Post-correspondence problem

Write a short note on:

Rice's theorem

Write a short note on: NP-hard problem

Write short notes on: NP-hard problem