Python · A Level 14

Finite State Machines and Regular Expressions

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 19 marks. Total 29 marks.

Name

Class

Date

Mark / 29

Section A

Circle the letter of the correct answer. One mark each.

1What does a finite state machine remember about the inputs it has already read?1
1. AEvery input in the order it arrived
2. BThe last three inputs only
3. CHow many inputs it has read
4. DOnly which state it is currently in
2In a state transition diagram, what is a double circle used for?1
1. AThe start state
2. BAn accepting state
3. CA dead state
4. DAn error message
3What is the difference between an acceptor and a Mealy machine?1
1. AAn acceptor has more states than a Mealy machine
2. BAn acceptor can only read binary
3. CA Mealy machine has no start state
4. DA Mealy machine produces an output on each transition, an acceptor only accepts or rejects
4What does the regular expression ab* match?1
1. AThe text ab repeated any number of times
2. BAn a followed by any number of b, including none
3. CAn a followed by at least one b
4. DEither a or b, once
5Which regular expression matches exactly three digits?1
1. A[0-9]+3
2. B3[0-9]
3. C[0-9]*3
4. D[0-9]{3}
6What does re.fullmatch(r'\d+', '12abc') return?1
1. AA match for 12abc
2. BNone, because the whole string is not digits
3. CAn error
4. DA match for 12
7What does it mean to say a language is regular?1
1. AEvery string in it has the same length
2. BIt has no more than ten strings
3. CIt can be described by a regular expression and accepted by a finite state machine
4. DIt can only use the letters a and b
8Why can a finite state machine not check that any string of brackets is balanced?1
1. AIt can only read each symbol once
2. BIt has no start state
3. CIt has a finite number of states, so cannot count an unlimited depth of nesting
4. DIt cannot read brackets
9An FSM tracks a binary number's remainder when divided by 3. How many states does it need?1
1. A3
2. B1
3. CAs many as there are bits
4. D2
10Which regex quantifier is lazy, matching as little as it can?1
1. A.+?
2. B.{3}
3. C.+
4. D.*

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

1DescribeDescribe what is meant by a finite state machine.3
2TraceThe state transition table shows a finite state machine with states S0, S1 and S2. S0 is the start state and S2 is the only accepting state. Trace the input 0110, giving the state after each symbol, and state whether it is accepted.3
```
current   input   next
S0        0       S0
S0        1       S1
S1        0       S0
S1        1       S2
S2        0       S2
S2        1       S2
```
3WriteWrite a regular expression that matches a time in the 24 hour clock format HH:MM, where HH is from 00 to 23 and MM is from 00 to 59, for example 07:45 or 23:59.4
4ExplainExplain why a finite state machine cannot be used to decide whether any string of brackets is balanced.3
5DiscussA game developer is deciding how to control the behaviour of an enemy character, which can patrol, chase the player, attack and flee. Discuss the use of a finite state machine for this.6

Mark scheme

Section A

1D2B3D4B5D6B7C8C9A10A

Section B

1 Describe what is meant by a finite state machine. 3

One mark for each of the following, to a maximum of 3.

It has a finite number of states and is in exactly one of them at a time
It reads inputs, and each input causes a transition to another (or the same) state
It has a start state, and may have accepting states or outputs

Model answer. A finite state machine is an abstract model that has a finite number of states and is in exactly one of them at any time. It reads a sequence of inputs, and each input causes a transition from the current state to the next state (which may be the same state). It has a start state and may have one or more accepting states, or produce outputs, to show the result.

2 The state transition table shows a finite state machine with states S0, S1 and S2. S0 is the start state and S2 is the only accepting state. Trace the input 0110, giving the state after each symbol, and state whether it is accepted. 3

One mark for each of the following, to a maximum of 3.

Starts in S0 and 0 leads to S0 (or follows the table correctly for the first symbols)
Shows the states S0, S0, S1, S2, S2 (or follows the table correctly to the end)
Concludes that it finishes in S2, an accepting state, so the input is accepted

Model answer. The machine starts in S0. Reading 0 from S0 gives S0. Reading 1 from S0 gives S1. Reading 1 from S1 gives S2. Reading 0 from S2 gives S2. The machine has finished in S2, which is an accepting state, so the input 0110 is accepted.

3 Write a regular expression that matches a time in the 24 hour clock format HH:MM, where HH is from 00 to 23 and MM is from 00 to 59, for example 07:45 or 23:59. 4

One mark for each of the following, to a maximum of 4.

Hours: first digit 0 or 1 followed by any digit, giving 00 to 19
Hours: or a 2 followed by 0 to 3, giving 20 to 23
Alternation between the two hour patterns, grouped with brackets
A colon followed by minutes: 0 to 5 then any digit

Model answer.

Python

import re

clock = re.compile(r"([01][0-9]|2[0-3]):[0-5][0-9]")
print(bool(clock.fullmatch("07:45")), bool(clock.fullmatch("24:00")))

The hours are either a 0 or 1 followed by any digit (00 to 19), or a 2 followed by a digit from 0 to 3 (20 to 23), joined with | and grouped in brackets. These are followed by a colon, then the minutes: a digit from 0 to 5 followed by any digit.

4 Explain why a finite state machine cannot be used to decide whether any string of brackets is balanced. 3

One mark for each of the following, to a maximum of 3.

To check the brackets the machine must keep count of how deeply they are nested
The nesting could be to any depth, but an FSM has a finite number of states
So it would run out of states and cannot count without a limit (a stack is needed)

Model answer. To check that brackets are balanced the machine needs to keep count of how many brackets are still open, which is how deeply they are nested. The nesting could go to any depth, but a finite state machine only has a fixed number of states, and its state is its only memory. It therefore runs out of states for a deep enough string and cannot count without a limit. A stack, which can grow as far as needed, is required instead.

5 A game developer is deciding how to control the behaviour of an enemy character, which can patrol, chase the player, attack and flee. Discuss the use of a finite state machine for this. 6

One mark for each of the following, to a maximum of 6.

Each behaviour is a state, such as patrol, chase, attack and flee
Events, such as seeing the player or low health, trigger transitions between states
Simple to design, draw and implement, for example as a table
Easy to test and debug, because the enemy is in exactly one known state at a time
Disadvantage: the number of states and transitions grows quickly as behaviour becomes more complex
A reasoned conclusion: suitable for simple behaviour, but predictable, so something more advanced may be needed for complex enemies

Model answer. The enemy's behaviours can each be a state: patrol, chase, attack and flee. Events such as seeing the player, getting close, or health dropping low cause transitions between the states, so the whole behaviour can be written as a simple state transition table or drawn as a diagram. This is simple to design and implement, and because the enemy is always in exactly one known state it is easy to test and debug. The disadvantage is that as the behaviour becomes more complicated the number of states and the number of transitions between them grows quickly and becomes hard to manage, and the behaviour can become predictable. A finite state machine is therefore a good choice for an enemy with a handful of simple behaviours, but a more advanced technique may be needed if the characters have to behave in complicated ways.