Test #1 review Flashcards
Main purpose of theory of computing
study the fundamental limits and capabilities of computation
Three areas of the theory of computing
Complexity theory, computability theory, and automata theory
complexity theory
classifies problem based on difficulty
computability theory
classifies problem if it can be solved or not
automata theory
does one model solve more problems than another
finite automata
regular languages
push down automata
context-free languages
turing machines
recursively enumerable languages
binary relation
subset of the cartesian product
reflexive relation
every element is related to itself
symmetric relation
if a is related to b, then b is related to a
transitive relation
if a is related to b and b is related to c, then a is related to c
equivelance relation
reflexive, symmetric, and transitive relations
function
a function is a relation R on AxB with the property that exactly one ordered pair in R whose first component is A
one to one function
each output value corresponds to exactly one input value
Deterministic Finite Automata
a device that has a processing unit with limited memory capacity and no auxiliary memory at all
DFA properties
- every move of a DFA can be determined by the input and current state
- input tape
- finite number of states
When is a string accepted by a DFA?
if the input ends on a favorable state
difference between regular and strong induction
regular you use k to prove k+1, in strong you assume the statement is true for all numbers up to k
