Theory of Computation Flashcards
Abstraction
- Abstraction is simplifying complex systems by removing unnecessary details and leaving only the essentials
- Representational abstraction = A representation made by removing unnecessary details
- Abstraction by generalisation = A grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type
Data abstraction
- Data abstraction focuses on hiding the implementation details of data structures and only exposing the necessary features
- Abstract data type = A high level description of a set of operations that can be performed on a data structure without specifying how
Provides operations and defines behaviour
Problem abstraction
- Problem abstraction = Where details are pulled away from the problem until it is represented in a solvable way
Works because a simplified problem is usually similiar to a problem that has already been solved
Decomposition, composition and automation
- Decomposition = Where a problem is divided into smaller sub-problems that can be solved individually
- Composition = Combining procedures to form a larger system - used in abstract data types like trees
- Automation = Putting abstractions of real world phenomena (models) into action to solve problems.
This is achieved by creating algortihms that are later implemented into code, implementing models into data structures and executing the code on the data structures
Finite State Machines
Finite state machines are machines that consist of a fixed number of possible states, a set of allowable inputs called the input alphabet that changes the state and a set of possible outputs
- Finite state automata = FSMs with no outputs
- Mealy machines = FSMs with outputs
FSMs are represented by state transition diagrams or state transition tables
Sets
A set is an unordered collection of values where each value occurs at least once
- Can be defined by listing its members; the set of Integers = {-3, -2, -1, 0, 1, 2, 3}
Common sets include:
- Empty set {}
- Natural numbers; N
- Real numbers; R
- Integers; Z
- Positive integers; Z+
- Negative integers; Z-
- Irrational numbers; Q
Set comprehension
Set comprehension describes the properties of the set’s members
S = {x * 3 | x ∈ ℤ ∧ x ≥ -3 ∧ x < 3} means x*3 is a member of the set such that x is an integer which is greater than or equal to -3 and is less than 3
- | means ‘such that’
- ∈ means ‘is a meber of’
- ∧ means ‘and’
- x*3 is the actual values of the set
Compact set representation
This is a shorthand way of describing sets
S = {0n 1n | n ≥ 1} means 0 and 1 appear n times in the string such that n is greater than or equal to 1
Set types
Finite set = Sets that contain a finite number of elements
Cardinality = How many members exist in a finite set
Infinite sets = Sets that contain an infinite number of members
These are divided into countable and non-countable infinite sets:
- Countable infinite = The number of items in the set can be counted with natural numbers
- Non-countable
infinite = Sets that contain a larger infinity of items that can’t be counted with natural numbers
eg. Set of Real numbers
Set terms
Subset = A set that only contains items from another set (symbol = ⊆, ‘is a subset of’)
Proper subset = A subset that doesn’t contain all the items from another set (symbol = ⊂, ‘is a proper subset of’)
Countable set = A set that has the same cardinality as some subset of the natural numbers.
Countable sets include finite sets and countably infinite sets.
Set Operations
Membership = Where an item is in a set (eg. 3 ∈ R; 3 is a member of the set of real numbers)
Union = Merging 2 sets into one - if an item appears in both sets, it will only appear once in the new set (symbol = ∪)
Intersection = The items that both sets share (eg. A = {1, 2, 3, 4, 5, 6} and B = {2, 4, 6}, the intersection is {2, 4, 6} and the symbol is ∩)
Difference = Only contains items exclusive to one set - not shared
(eg. A = {1, 2, 3, 4, 5, 6} and B = {2, 4, 6}, the difference is {1, 3, 5} and the symbol is \ or -)
Cartesian product = the set of all ordered pairs from 2 sets as (a,b), where a is from set A and b is from set B
(eg. A = {1, 2, 3, 4, 5, 6} and B = {2, 4, 6}, cartesian product = {(1,2),(1,4),(1,6),(2,2),(2,4),(2,6),(3,2),(3,4),(3,6),(4,2),(4,4),(4,6),(5,2),(5,4),(5,6),(6,2),(6,4),(6,6)} and symbol is X)
Regular expressions
Expressions used to specify a set of strings that satisfy given conditions
Both regular expressions and FSMs are equal ways to define a set
Metacharacters used:
- | means ‘alternatives / ‘or’ (a | b = a or b)
- ? indicates zero or one of the preceding element
(a? = “ “ or “a”) - [**] indicates zero or more of the preceding element
(a* = “ “ or “a” or “aa” etc) - (+) indicates one or more of the preceding element
(eg. a+ = “a” or “aa” or “aaa” etc) - () defines the scope of an operator and groups characters together
( (ab)* = “ “, “ab”, “abab” etc)
Regular language
Any language represented by a regular expression and any language that an FSM will accept
Context-Free languages
A context-free language is a set of strings and symbols that follow the rules of a
context-free grammar.
Context-free grammars describe which strings are and are not
possible in a language by laying out production rules.
Meta-language = a language that describes another language
Backus-Naur Form
BNF is a way of notating context-free languages
The left hand side of a BNF statement is defined by the right hand side
(eg. FullName ::= Title Forename Surname)
Symbols incldue:
- ::= means ‘is defined by’
- | means ‘or’
BNF consists of a set of terminals that can’t be broken down further and a set of non-terminals written as <name> that can be broken down into terminals</name>
Production rules = The syntax of a context-free grammar
(eg. Fullname = Title Forename Surname)
BNF supports recursion while regular expressions can’t.
(eg. Integer ::= Digit|Digit Integer where integer = 0 | 1 | 2 etc)
