Answer all the questions.
1) Define the following concepts formally:
(a) Finite Automata
(b) Non-Deterministic Finite Automata (NDFA)
(c) Kleene Closure of a set of expressions
(d) Regular Expression
(e) Regular Language
(f) Primitive Recursive Function
(g) Unsolvable Problem
(h) Turing Machine
(i) Universal Turing Machine
(j) Turing-Decidable Problem
(k) Moore Automata
(l) Context-free Language
(m) Pushdown Automata
(n) Halting Problem
(o) NP-Hard Problem
(p) Context-free Language
2) Show that language
L = { ap : p is positive prime integer} is not regular
3) Show that each of the following function is primitive recursive function.
(a) f (m, n) = 4mn
(b) fib (n), where fib (n) is defined by
fib (0) = 0
fib (1) = 1
fib ( n + 2) = fib (n) + fib (n + 1) , n ≥ 0
4) Construct one grammer for each of the following languages
(a) { ai bj ck | i = 2 j or j = 2k }
(b) { w ∈ { 0, 1}* : w = wR}
5) Construct one Turing Machine for calculating each of the following
(a) Llanguage { 0n 1n : n ≥ 1 }
(b) Function f (m, n) = m * n, where ‘*’ denotes multiplication