FORMAL LANGUAGE & AUTOMATA THEORY

Which of the following statements is/are false?

A. For every nondeterministic TM, an equivalent deterministic TM exists.
B. Turing recognizable languages are closed under union and complementation.
C. Turing decidable languages are closed under intersection and complementation.
D. Turing recognizable languages are closed under union and intersection.

(i) A and D only
(ii) A and C only
(iii) B only
(iv) C only

Which of the following problems is undecidable?

(i) DFA acceptance
(ii) NFA acceptance
(iii) The Halting Problem
(iv) Regular expression matching

A recursively enumerable language $L$ is recursive if:

(i) $L'$ is recursively enumerable
(ii) every sequence of moves of $T$ halts
(iii) Both (i) and (ii)
(iv) None of the above

Show that the function:

$$f(x,y) = x + y$$

is primitive recursive.

Write short notes on: Post Correspondence Problem.

Prove that the halting problem for Turing machines is recursively undecidable.

Write a short note on the Post Correspondence Problem.

Write a short note on Rice's Theorem with an application.

Write short notes on:

1. Post Correspondence Problem (PCP)
2. NP-hard problem

Write short notes on: NP-hard and NP-complete problems.

Write a short note on Universal Turing Machine.