Theory of comp Midterm 2 Questions and answers
what is not an interesting property of an algorithm?
Programming Language
Correctness
Existence
Complexity ** Answ** Programming language
what is the most "powerful" model of computation?
Register Machine
Linear Bounded Automata
Neo-Quantum machines
Turing machine ** Answ** Turning machine
True or false: The problem of finding the third symbol from the end of a string is solvable? **
Answ** True
What is the main characteristic of a decision problem? ** Answ** It has a Yes/No answer
True or false: The problem of finding the third symbol from the end of a string problem is a
decision problem? ** Answ** false
True or false: A decision problem is also an optimization problem? ** Answ** False
True or false: Considering only problem about strings limits the applicability of the theory? **
Answ** False
which field of computer science studies the efficiency of algorithms? ** Answ** Complexity
theory
, Is there an algorithm that checks if a string s is a substring of it self. ** Answ** True
What is not true about an alphabet?
it contains symbols
Its usually denoted with a capital Greek letter
It can be empty
words are made out of the symbols in it ** Answ** It can be empty
True or false: the empty word is an element of every formal language? ** Answ** False
True or false: the intersection of two languages is defined only if both are languages over the
same alphabet? ** Answ** False
If Σ is an alphabet, what is Σ *? ** Answ** The set of all words over the alphabet
True or false: The set of all even integers written in binary -i.e. as words over the alphabet {0,1) -
is a formal language? ** Answ** True
True or false: the set of all words with a length of a prime number is a formal language over any
alphabet? ** Answ** True
The problem of determining if a word w is an element of language L is called? ** Answ**
The word problem for L
True or false: Over every alphabet there are only finitely many words with a length of 1,000,000.
** Answ** True
True or false: an alphabet can be regarded as a formal language over itself? ** Answ** True
what is not (!) part of a DFA?
set of states
what is not an interesting property of an algorithm?
Programming Language
Correctness
Existence
Complexity ** Answ** Programming language
what is the most "powerful" model of computation?
Register Machine
Linear Bounded Automata
Neo-Quantum machines
Turing machine ** Answ** Turning machine
True or false: The problem of finding the third symbol from the end of a string is solvable? **
Answ** True
What is the main characteristic of a decision problem? ** Answ** It has a Yes/No answer
True or false: The problem of finding the third symbol from the end of a string problem is a
decision problem? ** Answ** false
True or false: A decision problem is also an optimization problem? ** Answ** False
True or false: Considering only problem about strings limits the applicability of the theory? **
Answ** False
which field of computer science studies the efficiency of algorithms? ** Answ** Complexity
theory
, Is there an algorithm that checks if a string s is a substring of it self. ** Answ** True
What is not true about an alphabet?
it contains symbols
Its usually denoted with a capital Greek letter
It can be empty
words are made out of the symbols in it ** Answ** It can be empty
True or false: the empty word is an element of every formal language? ** Answ** False
True or false: the intersection of two languages is defined only if both are languages over the
same alphabet? ** Answ** False
If Σ is an alphabet, what is Σ *? ** Answ** The set of all words over the alphabet
True or false: The set of all even integers written in binary -i.e. as words over the alphabet {0,1) -
is a formal language? ** Answ** True
True or false: the set of all words with a length of a prime number is a formal language over any
alphabet? ** Answ** True
The problem of determining if a word w is an element of language L is called? ** Answ**
The word problem for L
True or false: Over every alphabet there are only finitely many words with a length of 1,000,000.
** Answ** True
True or false: an alphabet can be regarded as a formal language over itself? ** Answ** True
what is not (!) part of a DFA?
set of states
