Theory of computation

Question 1

decomposition

Answer 1

breaking a problem down into sub problems making it easier to execute

Question 2

abstraction

Answer 2

Details are removed until it looks solvable
(simplifying a problem)

Question 3

algorithm

Answer 3

sequence of instructions that performs a specific task when followed

Question 4

Data abstraction

Answer 4

enables us to isolate how a compound data object is used from the details of how it is constructed.

Question 5

how do you build data abstractions

Answer 5

by combining data objects to form compound data, for example tree data structure

Question 6

how do you build a composition abstraction

Answer 6

by combining procedures to form compound procedures

Question 7

representational abstraction

Answer 7

removing unnecessary details

Question 8

information hiding

Answer 8

process of hiding all unnecessary details of an object

Question 9

procedural abstraction

Answer 9

represents a computational method

Question 10

functional abstraction

Answer 10

particular computation method is hidden

Question 11

how does automation achieve putting models into action to solve problems

Answer 11

1. creating algorithms
2. implementing the algorithms in program code (instructions)
3. implementing the models in data structures
4. executing the code.

Question 12

set and the alternative symbol for empty set

Answer 12

unordered collection of values in which each value occurs at most once.

Ø

Question 13

finite sets

Answer 13

elements can be counted off by natural numbers up to a particular number

Question 14

infinite set

Answer 14

counted off by the natural numbers.

Question 15

cardinality of a finite set

Answer 15

number of elements in a set

Question 16

Cartesian product of two sets

Answer 16

set of all ordered pairs

Question 17

regular expression

Answer 17

a way of describing a set

Question 18

describe the relationship between regular expressions and FSMs

Answer 18

Regular expressions and FSMs are equivalent ways of defining a regular language.

Question 19

regular language

Answer 19

any language that a FSM will accept

Question 20

when is a language called regular

Answer 20

if it can be represented by a regular expression.

Question 21

explain why BNF can represent some languages that cannot be represented using regular expressions.

Answer 21

BNF allows for the description of nested and recursive structures, whereas regular expressions are limited in their ability to handle such complex patterns.

Question 22

tractable

Answer 22

problems that have a polynomial (or less) time solution are called tractable problems.

Question 23

intractable

Answer 23

problems that have no polynomial (or less) time solution are called intractable problems.

Question 24

Heuristic methods

Answer 24

Heuristic methods are often used when tackling intractable problems.

Question 25

limits of computation

Answer 25

algorithmic complexity and hardware impose limits on what can be computed

Question 26

computable and non-computable problems

Answer 26

some problems cannot be solved algorithmically

Question 27

halting problem

Answer 27

Determining if a program will halt

demonstrates that there are some problems that cannot be solved by a computer.

Question 28

Explain the functionality of the * metacharacter

Answer 28

0 or more

Question 29

Explain the functionality of the + metacharacter

Answer 29

1 or more repetitions

Question 30

Explain the functionality of the ? metacharacter

Answer 30

0 or 1

Question 31

explain the functionality of the () metacharacter

Answer 31

to group regular expression

Question 32

explain the functionality of the | metacharacter

Answer 32

alternation

Question 33

importance of turing machines

Answer 33

Turing machines provide a model of computation and provide a definition of what is computable.

Question 34

universal turing machine

Answer 34

A Turing machine that can execute

Question 35

equivalence between a transition function and a state transition diagram

Answer 35

A state transition diagram represents the transitions between states in a finite state machine, while a transition function defines the specific transitions and their corresponding outputs in a mathematical form.