MIND YOUR GRAMMAR
ANOTHER NAME FOR A SUBSTITUTION RULE
What is a production?
THIS AUTOMATON IS EQUIVALENT TO CFG'S
What is a PDA?
THE REASON THAT TURING MACHINES ARE SO IMPORTANT
What is they provide a simple model of modeling a general-purpose computer?
DETERMINISTIC PDA'S ARE EQUIVALENT IN POWER TO NONDETERMINISTIC PDA'S
What is false?
JAY'S LAST NAME
What is Idema?
FOR A GRAMMAR TO BE TERMED AS AMBIGUOUS, A SINGLE STRING MUST HAVE TWO DISTINCT INSTANCES OF THESE
What are parse trees?
A PDA CONTAINS MEMORY IN THE FORM OF THIS DATA STRUCTURE
What is a stack?
TURING MACHINES CAN ACCEPT, REJECT, OR THIS
What is loop forever?
CFL'S ARE CLOSED UNDER INTERSECTION, COMPLEMENTATION, AND DIFFERENCE
What is false?
LOCATION OF HIDEOUS FOUNTAIN IN EUROPE
What is Vienna?
A SPECIAL FORM OF A GRAMMAR WHERE EACH NONTERMINAL IS REPLACED BY EITHER TWO NONTERMINALS OR ONE TERMINAL
THE STACK ALPHABET IS REPRESENTED BY THIS GREEK LETTER
What is gamma?
THIS LANGUAGE WAS PROVEN UNDECIDABLE THROUGH DIAGONALIZATION AND IS USED OFTEN TO PROVE OTHER LANGUAGES ARE UNDECIDABLE
What is ATM?
ALL TURING DECIDABLE LANGUAGES ARE ALSO TURING RECOGNIZABLE
What is true?
THE NAME OF TURING'S ADVISOR
What is Church?
A SERIES OF REPLACEMENTS TO PRODUCE A DESIRED STRING
What is a derivation?
What are uv^ixy^iz?
THE CONSTRUCTION PROOF PROCESS TO SHOW THAT ONE TM CAN BE IMPLEMENTED WITH ANOTHER
What is reduction?
IF A SOLUTION IS FOUND FOR ONE NP-COMPLETE PROBLEM, THEN WE CAN SOLVE ALL NP-COMPLETE PROBLEMS
What is true?
DR. DAVIS' MIDDLE INITIAL
What is A?
THE TYPE OF LANGUAGE THAT CAN BE REPRESENTED BY A GRAMMAR
What is a context-free language?
WHEN USING THE PUMPING LEMMA, i MUST BE IN THIS INTEGER RANGE
What is >= 0?
IN TERMS OF COUNTABILITY, INTEGERS ARE TERMED THIS
What is infinitely countable?
THERE ARE ONLY TWO CHOICES: P = NP OR
P IS A SUBSET OF NP
What is true?
DATE AND TIME OF OUR FINAL EXAM
What is ...?