4.4 [Theory of Computation] Flashcards
(30 cards)
What is an algorithm?
A sequence of steps that can be followed to complete a task and that always terminates.
What is pseudo-code?
A way of expressing an algorithm in the style of a program, but without worrying about language-specific syntax.
What is procedural decomposition?
Breaking down problems into a number of sub-problems, so that each sub-problem accomplishes an identifiable task.
Define abstraction.
Removing details until the problem is represented in a way that is possible to solve.
What is representational abstraction?
A representation arrived at by removing unnecessary details.
What is procedural abstraction?
Abstracting away actual values used in a particular computation, resulting in a computational method or a procedure.
What is functional abstraction?
Hiding the procedure, presenting a function that works but whose internal workings are hidden.
What is data abstraction?
Hiding the real data structure used in order to present a simpler, compound data structure.
What is composition abstraction?
Combining procedures to form compound procedures.
What is automation?
Putting models into action to solve problems.
What does a set represent?
An unordered collection of unique values.
What does the notation A = {1,2,3,4,5} represent?
Set A contains the values 1, 2, 3, 4, and 5.
What does the symbol Ø denote?
An empty set, a set containing no elements.
What is the cardinality of a finite set?
The number of elements in the set.
Define a proper subset.
A subset that contains some, but not all, elements of its parent set.
What is the Cartesian Product of two sets?
Where a is a member of A and b is a member of B.
What does the union of sets A and B represent?
A set containing the elements that are in either A or B.
What is a regular expression?
A way of describing a set that allows a regular language to be described.
What does the symbol * mean in regular expressions?
Zero or more of the preceding element.
What is a finite state machine (FSM)?
A model that has a finite number of states, and inputs are used to transition between states.
What is the purpose of a state transition diagram?
To represent an FSM with circles for states and arrows for transitions.
What is the difference between a finite state automaton (FSA) and a finite state machine (FSM)?
An FSA has a start state and a number of accept states.
What is the alphabet of an FSM?
The range of inputs it can accept.
What are context-free languages?
Languages that cannot be represented by regular expressions or finite state machines.
