Qualification Exam Theory Part

(Fall 2008 Topics)

1) Structural Induction, Induction

2) Logically Valid of $[;\forall;]$ and $[;\exists;]$ in $[; \exists z R(x,z) and \forall y R(x,f(x,y);]$

3) $[; L \cap K;]$ , $[;L \cup K;]$ $[; L -K ;]$ : context free closure

4) ${a^nb^{f(n)} | n \in N;]$ is not regular
and $a^nb^{kn}| n,k \in N;]$ is context free

5) The function f(n) :the number of perfect square numbers that < n,
f(n) is Primitive Recursive

6) The set of {m |p+q, when $[;p \in P;]$ and $[; q \in Q;]$ and P and Q are recursive enumerable sets } is a recursive enumerable set.

pC Blog