Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

a level computer studies > Unit 9 > Flashcards

Unit 9 Flashcards

1
Q

Define Finite State Machine

A

An abstract model of a computation used to design a range of computer programs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 5 states of FSMs?

A

States, transitions, transition conditions, start state and accept state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How can FSMs be used in language parsing?

A

You can enter a string into a FSM character by character, if the FSM is in the accept state at the end of the string that means that the string is valid for that language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the difference between a Mealy machine and a FSM?

A

A mealy machine generates an output for each transition. This means you can input a string and it will translate it for you.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What determines a mealy machine’s output?

A

The current state and the input from the user

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does it mean for a FSM to be deterministic?

A

Only a single transition can be assigned for each combination of state and input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How do you format the transition conditions on a mealy machine?

A

<input></input> / <output></output>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define language parsing

A

The process of analysing that a string of symbols conforms to the syntax rules of a language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the two ways to display a mealy machine?

A

As a diagram or a state transition table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the 4 areas shown in a mealy machine state transition table?

A

Input, current state, output, next state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Define set

A

A well defined collection of objects

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the name for an item in a set?

A

Element/member

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are two rules for members in sets?

A
  1. Each member can only occur once
  2. The members in a set must remain unordered
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How do you refer to a set and its corresponding members?

A

The set it referred to using an uppercase letter and the corresponding members are referred to using a lowercase letter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How are sets an example of abstraction?

A

Members in a set are grouped together as one object meaning you do not need to know every member of a set in order to reference it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What other area of logical computer science do sets link in with?

A

Boolean algebra

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the two ways of defining a set?

A
  1. Listing every member of the set
  2. Stating the properties that belong to members of the set but not by non-members
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Name a common set

A
  1. Integers
  2. Natural numbers
  3. Rational numbers
  4. Irrational numbers
  5. Ordinal numbers
  6. Real numbers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What does it mean if a common set symbol has a plus or a minus in superscript next to it?

A

That a further constraint has been applied to the set which is narrowing the field down to just positive or negative numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How many empty sets are there?

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How do you represent an empty set?

A

{ } or Φ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does ‘E’ mean?

A

is a member of

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What does ‘E’ with a line through it mean?

A

is not a member of

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What does ‘|’ mean?

A

such that

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What does ‘Λ’ mean?

A

and

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the section of the definition following an ‘Λ’ called?

A

The constraint for and

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What does AUB refer to?

A

All members that are in both A and in B or in A or in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

With does A intersection B refer to?

A

All members that are in A and in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does A\B refer to?

A

All members that are in A but not in B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What does it mean if A is a subset of B?

A

Every member of A is also a member of B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What does it mean if A is not a subset of B?

A

At least one member of A is not a member of B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is a proper subset?

A

When one set is a subset of the other but the two sets are not equal to one another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What does it means if A is a proper subset of B?

A

A is a subset of B but A is not equal to B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is a cartesian product of two sets?

A

The set of all ordered pairs from two sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Define cardinality

A

The number of elements in a finite set

36
Q

What is the notation for cardinality?

A

’| <set> |'</set>

37
Q

Define regular expression

A

A pattern used to identify sets of string

38
Q

How are regular expressions linked to sets?

A

Regular expressions act as set definitions and these sets are the acceptable strings for that language

39
Q

What does ‘|’ mean in regular expressions?

A

Or

40
Q

What does ‘*’ mean in regular expressions?

A

There are 0 or more of the preceding element

41
Q

What does ‘+’ mean in regular expressions?

A

There is 1 or more of the preceding element

42
Q

What does ‘?’ mean in regular expressions?

A

There is 1 or 0 of the preceding element

43
Q

What does ‘()’ mean in regular expressions?

A

The characters within the brackets act as one element and are grouped together

44
Q

What makes a language regular?

A

If it can be expressed by a regular expression and a FSM

45
Q

How do regular expressions translate to FSMs?

A

The characters acts as state transitions and each time a character is inputted the FSM will change state based on the rules of the regular expression. If the FSM is in the accept state at the end of the string then the string meets the rules of the regular expression.

46
Q

Define Turing machine

A

A general model of computation that can be defined to represent any computation

47
Q

What is a Turing Machine (in words not definitions)?

A

It is a thought experiment derived by Alan Turing that consists of a theoretical machine that can carry out any computer algorithm no matter how complex it was

48
Q

Why did Alan Turing think of the Turing Machine?

A

He was attempting to define computability and determine what was mathematically computable

49
Q

What 4 elements make up the program for a TM?

A
  1. A finite set of states in a state transition diagram
  2. A finite alphabet of symbols
  3. An infinite tape of marked off squares
  4. A sensing read/write head that can travel along the tape in either direction one square at a time
50
Q

What are the two parts of the machine in the TM?

A

The controller and the tape

51
Q

What does the controller in a TM do?

A

The controller decides what happens at each cell on the tape

52
Q

What other model of computation is the controller in a TM?

A

A mealy machine

53
Q

What 3 actions can the TM perform for each transition?

A
  1. Read the symbol on the tape
  2. Erase and write a new symbol on the tape
  3. Move the head left or right a single space
54
Q

What are the 3 parameters for the Mealy machine transitions that is the controller in the TM?

A
  1. The input
  2. The output
  3. The direction of movement
55
Q

What is a transition function?

A

A method of representing the transition arc between two states in a state transition diagram

56
Q

What symbol represents a transition function?

A

δ

57
Q

What is the format of a transition function?

A

δ (<current>, <input></input>) = (<next>, <output>)</output></next></current>

58
Q

What is the difference between a TM and UTM?

A

A UTM takes an additional input which is the program (aka the controller) so it can perform a range of different function

59
Q

What element of von Neumann’s architecture was inspired by the UTM?

A

The stored program concept

60
Q

What was the significance of the TM?

A

It provides a definition of what is computable and it can be mathematically proven that a TM is capable of computing anything that is computable

61
Q

What does BNF stand for?

A

Backus-Naur Form

62
Q

Define BNF

A

A formal notation used to describe the syntax rules of a programming language

63
Q

What type of language is BNF?

A

A meta-language

64
Q

Define meta-language

A

A language that describes a language

65
Q

Define context free language

A

An unambiguous way of describing the syntax of a language

66
Q

When are context free languages used?

A

When the syntax of a language is complex

67
Q

Why would you choose a context free language over regular expressions to describe syntax rules?

A

Regular expressions only work when there is a finite limit on the number of ways something can be organised and do not work for more complex languages

68
Q

Define terminal in terms of BNF

A

The final element that requires no further rules (cannot be broken down any further)

69
Q

What does ::= mean in BNF?

A

is defined as

70
Q

What does | mean in BNF?

A

or

71
Q

What does <> mean in BNF?

A

Surrounds category names

72
Q

Why is BNF used to represent programming languages?

A

Programming languages require strict and precise rules which can be represented by BNF syntax

73
Q

Define production rule

A

A single BNF statement

74
Q

What does it mean if a production rule is recursive?

A

The production rule calls itself and should be iterated through until the ‘stopping condition’ is reached and it does not call itself

75
Q

Define syntax diagram

A

A method of visualising rules written in BNF or other context free languages (one syntax diagram represents one production rule)

76
Q

Define reverse polish notation (RPN)

A

Another term for postfix notation

77
Q

What word describes the way in which we write mathematical expressions?

A

Infix notation

77
Q

Define prefix

A

Expressions that are written with the operators before the operands .e.g. + 2 3

78
Q

Define postfix

A

Expressions that are written with the operators after the operands .e.g. 2 3 +

79
Q

Define polish notation

A

Another way of describing prefix notation

80
Q

Why was polish notation created?

A

It was a simpler way of writing expressions that removed the need for brackets completely whilst still maintaining no ambiguity about how the expression should be executed

81
Q

Why polish notation adapted to become reverse polish notation?

A

It was a way of writing expressions that were in a convenient format for an interpreter to understand whilst translating lines of code

82
Q

Why is RPN more beneficial for interpreters?

A

An interpreter analyses operands first and then the operators so the operators should be on the right hand side of the expression

83
Q

What ADT is used to evaluate RPN expressions?

A

A stack

84
Q

Define in-order traversal

A

A method of extracting data from a binary tree that will result in an infix expressions

85
Q

Define post-order traversal

A

A method of extracting data from a binary tree that will result in a postfix expression

86
Q

Define pre-order traversal

A

A method of extracting data from a binary tree that will result in a prefix expression

a level computer studies (16 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions