Programming: Theory Of Computation Flashcards
With FSMs, what is the name given to a FSM with an output determined by its current state and inputs?
A mealy machine
What does Backus Naur Form consist of?
-A set of production rules
-A set of non-terminal symbols
-A set of terminal symbols
define representational abstraction
a representation where unnecessary details are removed
describe abstraction by generalisation
elements are grouped by common characteristics to produce a hierarchical relationship
describe information hiding
information about objects that don’t contribute to its essential characteristics are hidden
describe procedural abstraction
breaking down problems into a series of reusable procedures
describe data abstraction
details about how data is represented is abstracted
define problem abstraction
removing details about a problem being solved, until it is solvable. Often an abstracted problem has already been solved before.
describe decomposition
a problem is broken down into a series of sub problems that can be solved individually
describe composition
combining procedures to create a larger system
describe automation
abstracting real world phenomena and putting them in action to solve problems (modelling)
what are the symbols for empty sets?
{} and Ø
what is the cardinality of a set?
the number of values in a set
what is the symbol for a subset?
⊆
describe the concept of proper subsets
if a set is equal to another set, they are subsets of each other, but not proper subsets. symbol = ⊂
define countable sets
a set that has the same cardinality as some subset of natural numbers
how are non terminals identified?
angle brackets < >
sometimes called meta-components or syntactic variables
describe the meaning of a non terminal
text that represents another set of terminals or non terminals. terminals cannot be broken down any further
how are terminal values identified?
text without angled brackets (< >)
how can recursion occur with backus naur form?
a non-terminal can be used to describe itself, in combination with other terminals or non terminals
what is the correct syntax for defining the set of digits in backus naur form?
<Digit> : := 0|1|2|3|4|5|6|7|8|9
</Digit>
define a syntax diagram
a visual representation of a regular language
why can more values be represented by backus naur form than regular expressions?
regex cannot support recursion, where backus naur form can
define big o notation
a method of expressing the time complexity of an algorithm. the worst case scenario is always assumed.
how would a constant time complexity be represented in big O notation?
O(C)
how can logarithmic time complexity be represented using big o notation? give an example of an algorithm
O(log(n)) binary search
how can linear time complexity be represented in big o notation? give an example of an algorithm
O(n), linear search
how can a linear logarithmic time complexity be represented using big o notation? give an example algorithm
O(nlog(n)) merge sort
how can a polynomial time complexity be represented in big o notation? give an example algorithm
O(n^2) bubble sort or O(n^3)
how can an exponential time complexity be represented in big o notation?
O(2^n), intractable problems
how can a factorial complexity be represented in big o notation? describe how it can be recognised
O(n!), an intractable problem
describe the meaning of a tractable problem
a problem that can be solved within a useful period of time, a polynomial or less time complexity
describe an intractable problem
a problem that can theoretically be solved but not within a useful time period
what are used to solve intractable problems?
heuristic methods
define a heuristic method
a method of generating an approximate solution to an intractable problem, not necessarily the optimal solution
describe the halting problem
it is impossible to write an algorithm that determines if an algorithm will terminate given a specific input- some problems cannot be solved by computers.
describe a turing machine
a formal model of computation consisting of a finite state machine, a read write head and infinitely long tape.
what three things does a turing machine consist of?
a finite state machine, a read write head and infintely long tape in one direction, a pointer??
what is contained on the infinitely long tape of a turing machine?
cells containing a symbol or a blank space.
why is a turing machine more powerful than finite state machines?
they can utilise a greater range of languages due to the infinitely long tape.
how are the rules of a turing machine laid out?
transition functions
what form are transition functions written in?
delta(current state, symbol read) = (new state, written symbol, move (L/R))
how are turing machines limited?
they can only follow one finite state machine for the specific problem being solved.
how are universal turing machines (UTM) different to turing machines?
a universal turing machine is capable of representing any finite state machine meaning any computable problem can be solved using a UTM.
how do UTMs process using finite state machines?
a description of the FSM is read from the same infinite tape as the input data.
how do UTMs act as interpreters?
they read instructions of the FSM sequentially before executing operations with the input data.
why are turing machines important?
anything that is computable can be processed with a turing machine. therefore, turing machines can be used to prove that some problems can’t be solved by computers.
