Programming: Theory Of Computation

Question 1

With FSMs, what is the name given to a FSM with an output determined by its current state and inputs?

Answer 1

A mealy machine

Question 2

What does Backus Naur Form consist of?

Answer 2

-A set of production rules
-A set of non-terminal symbols
-A set of terminal symbols

Question 3

define representational abstraction

Answer 3

a representation where unnecessary details are removed

Question 4

describe abstraction by generalisation

Answer 4

elements are grouped by common characteristics to produce a hierarchical relationship

Question 5

describe information hiding

Answer 5

information about objects that don’t contribute to its essential characteristics are hidden

Question 6

describe procedural abstraction

Answer 6

breaking down problems into a series of reusable procedures

Question 7

describe data abstraction

Answer 7

details about how data is represented is abstracted

Question 8

define problem abstraction

Answer 8

removing details about a problem being solved, until it is solvable. Often an abstracted problem has already been solved before.

Question 9

describe decomposition

Answer 9

a problem is broken down into a series of sub problems that can be solved individually

Question 10

describe composition

Answer 10

combining procedures to create a larger system

Question 11

describe automation

Answer 11

abstracting real world phenomena and putting them in action to solve problems (modelling)

Question 12

what are the symbols for empty sets?

Answer 12

{} and Ø

Question 13

what is the cardinality of a set?

Answer 13

the number of values in a set

Question 14

what is the symbol for a subset?

Answer 14

⊆

Question 15

describe the concept of proper subsets

Answer 15

if a set is equal to another set, they are subsets of each other, but not proper subsets. symbol = ⊂

Question 16

define countable sets

Answer 16

a set that has the same cardinality as some subset of natural numbers

Question 17

how are non terminals identified?

Answer 17

angle brackets < >
sometimes called meta-components or syntactic variables

Question 18

describe the meaning of a non terminal

Answer 18

text that represents another set of terminals or non terminals. terminals cannot be broken down any further

Question 19

how are terminal values identified?

Answer 19

text without angled brackets (< >)

Question 20

how can recursion occur with backus naur form?

Answer 20

a non-terminal can be used to describe itself, in combination with other terminals or non terminals

Question 21

what is the correct syntax for defining the set of digits in backus naur form?

Answer 21

<Digit> : := 0|1|2|3|4|5|6|7|8|9
</Digit>

Question 22

define a syntax diagram

Answer 22

a visual representation of a regular language

Question 23

why can more values be represented by backus naur form than regular expressions?

Answer 23

regex cannot support recursion, where backus naur form can

Question 24

define big o notation

Answer 24

a method of expressing the time complexity of an algorithm. the worst case scenario is always assumed.

Question 25

how would a constant time complexity be represented in big O notation?

Answer 25

O(C)

Question 26

how can logarithmic time complexity be represented using big o notation? give an example of an algorithm

Answer 26

O(log(n)) binary search

Question 27

how can linear time complexity be represented in big o notation? give an example of an algorithm

Answer 27

O(n), linear search

Question 28

how can a linear logarithmic time complexity be represented using big o notation? give an example algorithm

Answer 28

O(nlog(n)) merge sort

Question 29

how can a polynomial time complexity be represented in big o notation? give an example algorithm

Answer 29

O(n^2) bubble sort or O(n^3)

Question 30

how can an exponential time complexity be represented in big o notation?

Answer 30

O(2^n), intractable problems

Question 31

how can a factorial complexity be represented in big o notation? describe how it can be recognised

Answer 31

O(n!), an intractable problem

Question 32

describe the meaning of a tractable problem

Answer 32

a problem that can be solved within a useful period of time, a polynomial or less time complexity

Question 33

describe an intractable problem

Answer 33

a problem that can theoretically be solved but not within a useful time period

Question 34

what are used to solve intractable problems?

Answer 34

heuristic methods

Question 35

define a heuristic method

Answer 35

a method of generating an approximate solution to an intractable problem, not necessarily the optimal solution

Question 36

describe the halting problem

Answer 36

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.

Question 37

describe a turing machine

Answer 37

a formal model of computation consisting of a finite state machine, a read write head and infinitely long tape.

Question 38

what three things does a turing machine consist of?

Answer 38

a finite state machine, a read write head and infintely long tape in one direction, a pointer??

Question 39

what is contained on the infinitely long tape of a turing machine?

Answer 39

cells containing a symbol or a blank space.

Question 40

why is a turing machine more powerful than finite state machines?

Answer 40

they can utilise a greater range of languages due to the infinitely long tape.

Question 41

how are the rules of a turing machine laid out?

Answer 41

transition functions

Question 42

what form are transition functions written in?

Answer 42

delta(current state, symbol read) = (new state, written symbol, move (L/R))

Question 43

how are turing machines limited?

Answer 43

they can only follow one finite state machine for the specific problem being solved.

Question 44

how are universal turing machines (UTM) different to turing machines?

Answer 44

a universal turing machine is capable of representing any finite state machine meaning any computable problem can be solved using a UTM.

Question 45

how do UTMs process using finite state machines?

Answer 45

a description of the FSM is read from the same infinite tape as the input data.

Question 46

how do UTMs act as interpreters?

Answer 46

they read instructions of the FSM sequentially before executing operations with the input data.

Question 47

why are turing machines important?

Answer 47

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.