Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
TOC
Theories of Computation
| Question | Answer |
|---|---|
| What is a matching problem vs finding problem (give examples)? | Matching: eg Given a string, say if its a valid password depending on conditions. Finding: Given a string, find email addresses and return as (x,y_, x= start position, y = length |
| What is Σ (in context)? | A finite set with at least two characters. |
| What is Σ*? | The set of all words (e.g strings of characters) |
| What is a language? | A subset of Σ* |
| What is the regex symbol for the empty word and nothing? | Empty word = ε Nothing = ø |
| What does E+ accept? | Any word that concatenates one or more words accepted by E, i.e EE*. |
| What does E? accept? | Either the empty word or E. |
| What is the definition of a regular language? | A language that can be represented by a regex. |
| What is a decision problem? | A problem that for any argument has a yes/no answer. |
| What makes a problem decidable? | It can be solved by a program. |
| What does a total DFA consist of? | A finites et of states, an initial state, a total transition function, and a set of accepting states. |
| What is a partial DFA? | A DFA where, if we get stuck, the word is rejected. This means failure happens earlier. |
| What is an NFA? | An automaton where it's possible to have two or more b-transitions out of the same state, and can have two or more initial states. |
| What do you to do an NFA to turn it into a DFA? | Determinize it. Each state in the DFA will be a set of states from the NFA. Each set of state in the union of all possible sets of next states. A state is accepting if some element is accepting. |
| What are epsilon transitions used for? | Allowing a 'silent transition', meaning a transition that doesn't read a character. |
| How is prior epsilon absorption done? | Make an NFA with the same states, same initial states, but show all slow transitions and slowly accepting states. (e.g, includes ε -> ε -> b as a single b) |
| What is Kleene's Theorem? | For any language L, the following are equivalent: there is a regex whose language is L, there's a DFA whose language is L, we can convert any regex into an equivalent DFA and vice versa. |
| How do we convert a regex into a DFA? | Convert the regex into an epsilon DFA. We remove the epsilon, giving an NFA, and determinize it. |
| What is structural induction? | Induction where we assume true for the children on a tree. |
| What is a minimal automata? | An automaton with as few states as necessary to represent a language. |
| What makes a state s reachable? | It is reachable when there's a path from an initial state to s. |
| What makes a state s hopeful? | It is hopeful when there's a path from s to an accepting state. |
| What makes two states s and t equivalent? | They have the same language, which is the set of words accepted when starting at the state. |
| What is a minimal partial DFA? | A DFA where each state is reachable, hopeful, and every pair of equivalent states equal. |
| How do you minimize a partial DFA? | Remove all unreachable and hopeless states, and identify each set of equivalent states. |
| What makes a set countable? | There's a bijection between N (set of natural numbers) and the set, e.g set of all primes. |
| What are some examples of uncountable sets? | Set of all bitstreams, real numbers, P(N) the power set of natural numbers ie. set of all sets of natural numbers. |
| Why must a non-regular language exist? | As the set of all regexes is countably infinite, and set of all languages is uncountable. |
| What is a grammar? | A formal way to describe a language, e.g a regex notation. |
| What is the Backus-Naur Form? | A more precise way of writing a context-free grammar describing a language. It consists of |
| What is a variable, token and production? | Variable: A symbol. Tokens: Elements of Σ. Production: Each line of a grammar. |
| What is a context free grammar? | A general grammar, containing a finite set of variables, a finite set of tokens, a finite set of productions and start variables. |
| What is a context free language? | The language of a CFG insisting of all derivable words. |
| What is a derivation tree used for? | A leftmost/rightmost derivation, where you replace the leftmost/rightmost occurrence of a variable. |
| How do you derive a word w? | Begin with the start variable. At each step, replace the start variable according to a rule in the grammar by a string of variables and tokens. At the end, we should only have tokens, so we have a word w. |
| What is Chomsky normal form? | Rules with the following form: A ::= BC A ::= a Allow S ::= Empty word. When we derive a word, either it's empty, or it's non empty with a length n and the derivation has 2n-1 ssteps. |
| Why must a non-context free language exist? | There are only countably many CFGs, but uncountably many languages. |
| What is the worst case complexity of a program determined by? | Inputs of the specified size that take the most time. An upper bound for the worst case is an upper bound for all inputs that size. |
| What is the best case complexity of a program determined by? | Inputs that take the least time. |
| What is the average case complexity of a program determined by? | The expected case for inputs of a given size - requires probability information. |
| What is a Turing Machine? | A simple model of computation: it is an infinite tape, with a head that moves left/right, and it read/writes characters. |
| What does a Turing Machine contain? | A tape alphabet, an input alphabet, a set of return values. |
| What is parity checking? | e.g checking whether the number of a's is even or odd. |
| Define a macro. | A macro is a single instruction that abbreviates an entire program, each with their own return set. |
| Name three variations of Turing Machines and how they work. | Auxiliary characters (allows for extra characters, e.g a'), Two-tape machine (Uses a main tape and an auxiliary tape, with their own head), 2-Dimension TM (An infinite sheet, includes all instructions and Up and Down) |
| How do you turn fancy TMs into simple TMs? | 1. Give a relationship between fancy and simple configurations. 2. Convert initial simple configuration to one representing initial fancy. 3. For each fancy, say how to mimic it with a simple program. 4. Given a simple, say how to convert it to fancy. |
| What is the complexity class P? | The class of decision problems that can be solved on a TM in polynomial time. |
| What is a Non-Deterministic TM (NTM)? | A TM with the same set of instructions as a regular TM, but includes a "choose" function. |
| What makes a decision problem in NP? | There is a polynomial time NTM whose language is L. |
| What makes a language NP-Hard and NP-Complete? | NP-Hard: Every language in NP reduces to it in polytime. NP-Complete: It is in NP and also NP-Hard. |
| What is Church's thesis? | Any decision problem on words that can be decided by an algorithm can be decided by a TM. |
| Define Primitive Java. | Primitive java has one type, nat, for natural numbers, infinitely many variables, and can create, increment, decrement variables, can do conditionals, and fixed repetitions. |
| Define Basic Java. | Basic Java extends Primitive java with while loops. |
| What makes a decision problem semidecidable? | When there exists an algorithm/TM that when given a word, returns true if in the language, but runs forever if not. |
| What is the Halting Problem, and by extension, Halting Theorem? | Given a nullary program, say whether it halts or hangs, and prove this problem is decidable. We can prove this can't be done, i.e "Halting Theorem" |
| What does it mean to reduce a problem P to a problem Q? | Say how to solve problem P, given a solution to Q. |
| Say we reduced decision problem P to Q. 1. If Q is decidable, what is P? 2. If P is undecidable, what is Q? | 1. P is decidable. 2. Q is undecidable. |
| What makes two pieces of code semantically equivalent? | They are semantically equivalent when, for any input provided to them, they give the same output. |
| What is Rice's theorem? | With two exceptions, semantic properties of code are undecidable. |
| How do you show that a property is not semantic? | Give semantically equivalent pieces of code M and N, where M has the property, and N does not. |
| What are the two exceptions in Rice's theorem? | 1. For a code type nat, does the code return a number greater than itself? Impossible, so it's semantic. Decidable: return False. 2. For a code type nat, does it hang or return a number equal to itself? Always, so it's semantic. Decidable: return True. |
Created by:
user-2035207