1. Which of the following statements on computational complexity theory foundations are correct A) A logic expression IFF may stand for if and only if. B) It is unknown whether P and NP are actually the same class. C) Context Free Languages are generated by Context Free Grammars. D) NP is the class of languages that have polynomial-time verifiers. 2. Which statements on computational complexity theory foundations are correct A) For Deterministic Finite State Machines no randomness means perfect repeatability. B) In graph theory vertices are sometimes also referred to as nodes. C) Equivalence between variations of Turing Machines can be understood in terms of computing efficiency. D) The Halting Problem for a Turing Machine is decidable.

3. Which statements are correct A) The linear complexity class is not considered polynomial time. B) The Turing Machine is a computational model that can be considered as a model for all computers. C) A language is context-free if for example there exists a Pushdown Automaton that recognizes it, but also in other cases. D) For a computable function the Turing Machine will always halt. 4. Which statements on computational complexity theory foundations are correct A) A language is regular if and only if it is recognized by some Finite State Machine. B) A language is Turing decidable if and only if there exists some enumerator that enumerates it. C) A problem is in the NP complexity class if there is a Nondeterministic Turing Machine that will solve it in polynomial time. D) The SAT problem (propositional satisfiability problem) is an NP-complete problem. 5. Which of the below statements on computational complexity theory foundations are correct A) Both the FSM and FSA acronyms refer to the same concept, the Finite State Machine (Automaton). B) In regular expressions star and union operators bind tighter than the concatenation operator. C) Two grammars generating the same language may not be equivalent. D) Only certain relation symbols have arity. 6. Which of these statements are correct A) There exist questions about regular languages that are not decidable. B) We do not know yet whether the P class is equal or not to the EXPTIME class. C) Turing recognizable languages form a subset of decidable languages. D) For every Nondeterministic Finite State Machine there is an equivalent Deterministic Finite State Machine. 7. Which of the statements below are correct A) Turing Machines and Lambda Calculus are not equivalent in power. B) Turing Machines can move the head over the tape by more than one cell at each step of their operation. C) Computation of a deterministic Turing Machine can be shown on a tree in contrast to computation of a Nondeterministic Turing Machine. D) A problem if two grammars are equivalent is not decidable. 8. Which of the statements below are correct A) Pumping lemma for context free languages may be used to prove that certain languages are not context free. B) There exist different variations of Turing Machines definitions which are not equivalent. C) All languages are Turing recognizable. D) A language is a set of strings.

9. Which statements are correct A) Any arbitrary problem can be expressed as a language. B) Not every regular language is context free. C) A regular expression cannot be defined using recursion. D) Regular languages are not equivalent with Finite State Machines. 10. Which of the following statements are correct A) All different variations of Turing Machines are equivalent in computing capability. B) The Turing Machine is not necessarily deterministic. C) It is certain that the PSPACE class is not equal to the EXPSPACE class. D) Accordingly to the Church-Turing Thesis an algorithmically computable problem is a problem computable by a Turing Machine.

11. Which statements on computational complexity theory foundations are correct A) Decidable questions are such questions for which one can write a program that will always terminate. B) If P and NP classes would be the same it doesn't necessarily mean that for all problems in the NP class there would exist polynomial time solutions. C) When a problem's solution can be verified in a polynomial time it can be classified in the NP complexity class. D) The big-O notation in complexity theory stands for an order of the function characterizing computational resources consumption growth rate on an input size growth.

12. Which of the following statements are correct A) The set of rational numbers is uncountably infinite. B) Gdel's Incompleteness Theorem states that number theory is undecidable. C) In the Chomsky Hierarchy type-3 languages are regular, type-2 languages are context-sensitive, type-1 languages are context-free, while type-0 languages are recursively enumerated. D) The Recursion theorem can be formulated in the fixed point version. 13. Which of the following statements on computational complexity theory foundations are correct a) Although most problems are in NP there are problems in PSPACE for which there is no known NP algorithm. b) The P class is certainly not equal to the EXPTIME class. c) For Turing Machines there may be two final states. d) A minimal Turing Machine is such that there is no an equivalent TM with a shorter description.

_________________________________________________________________________________________

14. Which of the statements below on computational complexity theory foundations are correct A) Enumeration is not enough to describe a language. B) Finding of an efficient (polynomial) solution for any NP-complete problem on a Deterministic C) Turing Machine will immediately prove that NP and P classes are the same. In Linear Bounded Automata the tape is limited to the size of the input (which is equivalent to a head of the Turing Machine being limited to move beyond the input part of the TM tape). D) Every context-free language is in the P complexity class. 15. Which statements on computational complexity theory foundations are correct A) There are no languages which would not be Turing recognizable. B) There exist questions about context-free languages that are not decidable. C) Regular languages form a subset of context-free languages. D) Pumping lemma for regular languages cannot be used to prove that certain languages are not regular. 16. Which of these statements are correct A) It is possible that the NP class is equal to the EXPTIME class. B) A Finite State Machine is defined by a 6-tuple. C) Regular expressions are not equivalent with regular languages. D) The Turing Machine can be used to decide a language, to recognize a language or to compute a function. All different variations of Turing Machines are equivalent in computing capability.

17. Which if these statements on computational complexity theory foundations are correct

A) Space complexity is measured in the number of cells on the tape that the Turing Machine will visit during computation

B) Rules for transforming one statement into another while preserving truth are referred to as rules of inference or deduction

C) The set of all languages is uncountable infinite

D) For any transformation function on Turing Machines there will never exist a Turing Machine which would be unchanged by the transformation

18. Which of the statements below on computational complexity theory foundations are correct

A) Finding of an efficient (polynomial) solution for any NP-complete problem on a Deterministic Turing Machine will immediately prove that NP and P classes are the same.

B) In Linear Bounded Automata the tape is limited to the size of the input (which is equivalent to a head of the Turing Machine being limited to move beyond the input part of the TM tape).

C)Enumeration is not enough to describe a language.

D) Every context-free language is in the P complexity class.

19. Which of the statements below are correct

A) Lambda Calculus and Turing Machines are computational models answering the question on what does computable mean.

B) Predicates output either true or false.

C) In Nondeterministic Finite State Machines the next state is chosen at random, which is equivalent to all next states being chosen in parallel.

D) Every multi-tape Turing Machine has an equivalent single-tape Turing Machine.

20. Which of the following statements are correct

A)A language is in NP if it is decided by some Nondeterministic Polynomial-Time Turing Machine, as well as in other cases.

B) The P complexity class is either a subset of the PSPACE class or both classes are the same.

C) A fixed point of a function is a value that is left unchanged by repeated applications of the function.

D) Axioms require proofs of their statements.

21. Which of these statements are correct

A) Each regular expression defines a language.

B) Adding nondeterminism to Turing Machines makes them non-equivalent to Deterministic TMs.

C) Not every problem about regular languages is decidable.

D) Every Context Free Language can be generated by a grammar in the Chomsky Normal Form.