SLR7 Finite State Machines

Question 1

What is a finite state machine?

Answer 1

A model of computation, used to design computer programs and sequential logic circuits

Question 2

What is it a model of?

Answer 2

An abstract model of how a machine reacts to external events

Question 3

How many states can a finite state machine be in at one time?

Answer 3

Can only be in one of a finite number of states at any one time, which changes based on trigger conditions

Question 4

What do you use to visualise FSMS?

Answer 4

State transition diagrams

Question 5

How is a state represented?

Answer 5

A circle with text in

Question 6

How is a start state represented?

Answer 6

A circle with an arrow coming into it

Question 7

How do you represent an accept state?

Answer 7

Circle inside circle

Question 8

What are tranisiton conditions?

Answer 8

Each transition must have a transition condition
Structured as ‘transition/input’ which causes the state following the direction of the transition arrow

Question 9

What is a mealy machine?

Answer 9

It is an FSM with an output

Question 10

What is a mealy machines output determined by?

Answer 10

its current state and its current input

Question 11

What are regular expressions?

Answer 11

An equivalent way of defining a regular language

Question 12

When is a language considered regular?

Answer 12

When it can be represented by a regular expression
When a FSM will accept the language

Question 13

What are some things you might want to use FSM to model?

Answer 13

• digital systems
• compilers
• network protocols

Question 14

What is finite state automation?

Answer 14

• an FSM that has no output
• has a start state and a set of accept states which define whether it accepts or rejects finite strings or symbols

Question 15

What is deterministic FSM automation?

Answer 15

if the next state is uniquely determined by the input when in a specific state

Question 16

What happens when data input into an FSM is valid?

Answer 16

the FSM will terminate in an accepting state

Question 17

What is a set?

Answer 17

an abstract data type which contains unordered unique values
sets can contains other sets

Question 18

What is set comprehension?

Answer 18

A different way of creating a set - rather than specifying all of the items individually, we can select what we want from a more general set

Question 19

What does | mean?

Answer 19

it means ‘such that’

Question 20

What does e mean?

Answer 20

means ‘is drawn from’

Question 21

What does ^ mean?

Answer 21

means ‘and’

Question 22

What does a simple set comprehension look like?

Answer 22

A = { x | xeN ^ x>1}

Question 23

How does a set comprehension look?

Answer 23

S = {Instruction | x e Defined Set ^ x satisfies condition}

Question 24

How do you represent an empty set?

Answer 24

{} or zero with a cross through it

Question 25

What is compact set representation?

Answer 25

an efficient way of describing sets

Question 26

What are the most common symbols in regular expression?

Answer 26

= vertical bar separates alternatives
? = question mark shows that there are zero or one of the preceding elements
* = asterisk indicates that there are zero or more of the preceding elements
+ = a subscript plus indicates that there are one or more of the preceding element

Question 27

What could (Edward)(Eddie)(Ed) represent?

Answer 27

Edward, Eddie, Ed

Question 28

What could (D|d)is(c|k) represent?

Answer 28

“Disc”, “disc”, “Disc”, “Disk”

Question 29

What could Dialg(ue)?

Answer 29

Dialog, Dialogue

Question 30

What does ab* represent?

Answer 30

a, ab, abb, abbb

Question 31

What does a*b represent?

Answer 31

ab, aab, aaab

Question 32

What can regular expression be used for?

Answer 32

• to match patterns in text files (e.g., when searching for a particular word within a program)
• by compilers to recognise the correct form of a variable name or the syntax of a statement
• by programmers to validate user input (e.g., to check that a postcode or an email address is in the correct form)

Question 33

What are the main set definitions?

Answer 33

• A = {N} = natural numbers
  
  • B = {Z} = integer numbers
  • C = {Q} = rational numbers
  • D = {R} = real numbers
    … Means and so on

Question 34

What is a finite set?

Answer 34

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

Question 35

What is a infinite set?

Answer 35

• can be countable or uncountable
• the difference between natural and real number, natural numbers are countably infinite

Question 36

What are countably finite sets?

Answer 36

the number of elements in the set

Question 37

What is the cardinality of a finite set?

Question 38

What is the Cartesian product of sets?

Answer 38

• written as A x B
• spoken as A “cross” B
• is a set of all ordered pairs (a, b) where a is a member of A and b is a member of B

Question 39

Define countable?

Answer 39

a set which can be counted off against a subset of the natural numbers e.g., all of the natural numbers up to a fixed limit