4: Theory of Computation Flashcards
Representation Abstraction
A representation arrived at by removing unnecessary details
Abstraction by Generalisation or Categorisation
Grouping by common characteristics to arrive at a hierarchal relationship of the ‘is a kind of’ type
Information Hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
Procedural Abstraction
The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method - a procedure
Functional Abstraction
The result of a procedural abstraction is a procedure, not a function. To get a function requires yet another abstraction, which disregards the particular computation method
Data Abstraction
Details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects
Problem Abstraction / Reduction
Details are removed until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved
Decomposition
Procedural decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided
Automation
Putting models (abstraction of real-world objects / phenomena) into action to solve problems
Finite Set
One whose elements can be counted off by natural numbers up to a particular number
Infinite Set
One whose elements cannot be counted off by natural numbers up to a particular number
Countably Infinite Set
One that can be counted off by the natural numbers
Cardinality of Finite Set
The number of elements in the set
Cartesian Product of Sets
X x Y (X cross Y) is the set of all ordered pairs (x, y) where x is a member of X and y is a member of Y
Proper Subset
If A ⊂ B then B contains everything in A, but there is at least one element in B that is not in A
Subset
⊆ includes both ⊂ and =
Countable Set
A set with the same cardinality as some subset of natural numbers
Set Difference Operation
A\B = {x : x ∈ A and x ∉ B}
Regular Expressions Metacharacters (5)
- * means 0 or more repetitions
- + means 1 or more repetitions
- ? means 0 or 1 repetitions (i.e. optional)
- | means alternation
- () used to group regular expressions
Relationship between Regular Expressions & FSMs
They are equivalent ways of defining a regular language
Regular Language
A language is regular if it can be represented by a regular expression
BNF Production Rules (4)
- Chevrons denote a non-terminal symbol, which has another set of production rules to define it
- Symbols without chevrons are terminal
- The pipe symbol is a metacharacter denoting alternatives
- <fullname> :: =<title> Moloney|<title> Pope
<title> :: =Mr|Mrs
BNF Syntax Diagram for <date> ::= <day-name><month-name>|<day-name><month-name><year>
BNF vs Regular Expressions (3)
- All regular languages are context-free but the reverse is not true
- Any regular expression can be converted to a set of BNF production rules
- As an FSM has a finite number of states, a context-free language is required when an infinite number of elements in a string must be counted
