Rise of the Machines
Grammar Police
Comparative Languages
Potpourri
100
In an automaton, ending in this state means the input string is in the language for the machine.
What is the accept state?
100
S → x is an example of one of these.
What is a rewrite rule?
100
NFAs accept this type of language.
What is regular?
100
This term is used to describe the size of the set of natural numbers.
What is countable? (or countably infinite)
200
A machine that has exactly one next state for a given current state and input character.
What is a DFA (deterministic finite automaton)?
200
This type of grammar corresponds to a DFA.
What is a regular grammar? [Since there is a theorem that every language accepted by a DFA is generated by a regular grammar.]
200
This operator indicates zero or more instances of the string it is applied to.
What is Kleene Star?
200
This commonly used set of numbers is known to be uncountable.
What is the real numbers? (or an interval or complex)
300
This allows for multiple next states for the same input and current state.
What is nondeterminism? (or NFA)
300
The restriction on the left side of any rewrite rule in a context-free grammar.
What is "must be exactly one nonterminal"?
300
This language is generated by the following grammar
S → xS
S → λ
What is xn
300
This is the most useful proof technique in Theory of Computation.
What is induction? (also acceptable: Proof by Contradiction)
400
This machine has a stack.
What is a PDA? (push down automaton)
400
A form of context-free grammar in which the right side of every rewrite rule is either two nonterminals or one terminal.
What is Chomsky Normal Form?
400
This is the nonempty finite set of symbols from which the strings to be analyzed by a DFA are constructed.
What is the alphabet? (Σ)
400
This is the name given to an arc that indicates a change of state.
What is a transition?
500
Not counting the Terminator, this is the most powerful machine.
What is a Turing Machine?
500
Me and him was going to the movie because it was funner than doing homework.
What is bad grammar?
500
This theorem gives the form of a string that must be part of any context-free language that is not finite.
What is the pumping lemma?
500
(p, x, s; q, y)
What is a transition from state p to state q that reads x, pops s and pushes y?
M
e
n
u