Monday, November 17, 2008

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) [; f: {a^nb^{f(n)} | n \in N;] is not regular
and [;f: 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.

No comments:

Post a Comment