COSC 3340 Final Exam Questions and
Answers8
Which of the following is NOT a valid string for the regular expression a*b*c*? - ANSWERS-
abccba
Regular expressions are more like program syntax - ANSWERS-True
The set of strings accepted by a DFA is called the - ANSWERS-Alphabet
Regular languages are not closed under intersection. - ANSWERS-False
If a problem cannot be solved even using a Turing Machine then it implies that the problem is -
ANSWERS-undecidable
Basic Turing Machine is equivalent to all of the following: - ANSWERS-1. TM + storage
2. Multitrack TM
3. Multi-tape TM
4. Non-deterministic TM
TMs can be used as both: - ANSWERS-Language recognizers and calculators/computers
Recursive languages are closed under __ - ANSWERS-Complementation, Union, intersection,
concatenation, etc.
, Are recursively enumerable languages closed under complementation? - ANSWERS-No. They
are closed under union, intersection, concatenation
A language is a collection of sentences of finite length all constructed from a finite alphabet of
symbols. - ANSWERS-True
Empty string is represented by - ANSWERS-ε (epsilon)
Explicit ε transitions between deferent states introduce non-determinism: - ANSWERS-True
String 00110100 will be accepted by a DFA that accepts? - ANSWERS-1010 as substring
The machine that can exist in only one state at any given time is known as: - ANSWERS-DFA
The machine that can exist in multiple state at any given time is known as: - ANSWERS-NFA
An intermediate result that we show to prove a larger result is known as: - ANSWERS-lemma
An NFA is defined by 5-tuple: - ANSWERS-True
Study of abstract computing devices or machines is known as: - ANSWERS-Automata theory
A DFA is defined by 3-tuple: - ANSWERS-False (is defined by 5-tuple)
A DFA that accepts any string that ends with 10 will accept which of these strings? - ANSWERS-
00000010
Answers8
Which of the following is NOT a valid string for the regular expression a*b*c*? - ANSWERS-
abccba
Regular expressions are more like program syntax - ANSWERS-True
The set of strings accepted by a DFA is called the - ANSWERS-Alphabet
Regular languages are not closed under intersection. - ANSWERS-False
If a problem cannot be solved even using a Turing Machine then it implies that the problem is -
ANSWERS-undecidable
Basic Turing Machine is equivalent to all of the following: - ANSWERS-1. TM + storage
2. Multitrack TM
3. Multi-tape TM
4. Non-deterministic TM
TMs can be used as both: - ANSWERS-Language recognizers and calculators/computers
Recursive languages are closed under __ - ANSWERS-Complementation, Union, intersection,
concatenation, etc.
, Are recursively enumerable languages closed under complementation? - ANSWERS-No. They
are closed under union, intersection, concatenation
A language is a collection of sentences of finite length all constructed from a finite alphabet of
symbols. - ANSWERS-True
Empty string is represented by - ANSWERS-ε (epsilon)
Explicit ε transitions between deferent states introduce non-determinism: - ANSWERS-True
String 00110100 will be accepted by a DFA that accepts? - ANSWERS-1010 as substring
The machine that can exist in only one state at any given time is known as: - ANSWERS-DFA
The machine that can exist in multiple state at any given time is known as: - ANSWERS-NFA
An intermediate result that we show to prove a larger result is known as: - ANSWERS-lemma
An NFA is defined by 5-tuple: - ANSWERS-True
Study of abstract computing devices or machines is known as: - ANSWERS-Automata theory
A DFA is defined by 3-tuple: - ANSWERS-False (is defined by 5-tuple)
A DFA that accepts any string that ends with 10 will accept which of these strings? - ANSWERS-
00000010
