Font size
WorksheetsCSAL 313_MIDTERM EXAM
Total questions: 15
Worksheet time: 8mins
It is the study of abstract computing devices, or “machines”
(a)
Who is the Father of Modern Computer Science?
(a)
The machine can exist in multiple states at the same time.
(a)
A (a) is a collection of sentences of finite length all constructed from a finite alphabet of symbols
The machine can exist in only one state at any given time.
(a)
A (a) is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
(a) is the simplest machine to recognize patterns.
Which process is being required to obtain the minimal version of any DFA?
(a)
What do you call this icon ∑?
(a)
In DFA what do you call this icon ∅?
(a)
Which one of the following is FALSE?
There is unique minimal DFA for every regular language
Every NFA can be converted to an equivalent PDA.
The complement of every context-free language is recursive.
Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The set of all strings containing the substring 00.
The set of all strings containing at most two 0’s.
The set of all strings containing at least two 0’s.
The set of all strings that begin and end with either 0 or 1.
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
n - 1
n
n + 1
2n - 1
A deterministic finite automaton (DFA) D with alphabet {a,b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
The definition of a language L with alphabet {a} is given as following. L={a^nk | k>0, and n is a positive integer constant} What is the minimum number of states needed in DFA to recognize L?
k+1
n+1
2^(n+1)
2^(k+1)
