Theory of Computation Crossword
This printable crossword puzzle on the topic of Computer Science & Technology has 22 clues. Answers range from 3 to 19 letters long. This crossword is also available to download as a Microsoft Word document or a PDF.
Description
Formal definition is a 5-tuple
Like an NFA with a stack
class of regular languages is closed under this operation
Context-Free Languages are closed under this operation
Nondeterministic Finite Automata
If you can create a DFA for this language then it is _________
lemma used to prove a language is NOT regular
Often used to express programming languages and natural languages
all rules have form A -> BC and A -> a
All Context-Free Languages have these
Formal definition is a 7-tuple
tape alphabet
string alphabet
A language that some Turing Machine recognizes is _________-_____________
A language that has a Turing Machine decide it is ________-__________
decidable languages are closed under this operation
Language A is turing-recognizable and the complement of A is Turing-recognizable then A is ____________
Rice's Theorem is one way to prove a language is ____________
Recognizable languages are not closed under this operation
Dissociative drug
Theory about how long it takes a Turing Machine to decide
This complexity class is closed under Union
