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

$$ Only certain relation symbols have arity.

$$ Two grammars generating the same language may not be equivalent.

$$ In regular expressions star and union operators bind tighter than the concatenation operator.

$$ Both the FSM and FSA acronyms refer to the same concept, the Finite State Machine $($Automaton$).$

Which of these statements are correct

$$ A Finite State Machine is defined by a $6-$tuple.

$$ Regular expressions are not equivalent with regular languages.

$$ It is possible that the NP class is equal to the EXPTIME class.

$$ The Turing Machine can be used to decide a language, to recognize a language or to compute a function.

Which of the following statements are correct

$$ It is certain that the PSPACE class is not equal to the EXPSPACE class.

$$ All different variations of Turing Machines are equivalent in computing capability.

$$ The Turing Machine is not necessarily deterministic.

$$ Accordingly to the Church$-$Turing Thesis an algorithmically computable problem is a problem computable by a Turing Machine.

$$

Which statements given below are correct

$$ The Turing Machine is a computational model that can be considered as a model for all computers.

$$ The linear complexity class is not considered polynomial time.

$$ A language is context$-$free if for example there exists a Pushdown Automaton that recognizes it$,$ but also in other cases.

$$ For a computable function the Turing Machine will always halt.

Which following statements on computational complexity theory foundations are correct

$$ Decidable questions are such questions for which one can write a program that will always terminate.

$$ 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.

$$ When a problem's solution can be verified in a polynomial time it can be classified in the NP complexity class.

$$ 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.

Which of the following statements on computational complexity theory foundations are correct

$$ It is unknown whether P and NP are actually the same class.

$$ Context Free Languages are generated by Context Free Grammars.

$$ NP is the class of languages that have polynomial$-$time verifiers.

$$ A logic expression IFF may stand for if and only if$.$

Which of the following statements given below are correct

$$ The set of rational numbers is uncountably infinite.

$$ 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.

$$ G$$del$\text{'}$s Incompleteness Theorem implies that number theory is undecidable.

$$ The Recursion theorem can be formulated in the fixed point version.