Revision Library

revisionlibrary.co.uk

A-Level · AQA

A2.9 Data Representation and Theory of Computation

AQA 7517 · Calculators not allowed · about 150 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

Data representation and the theory of computation

Original questions written for Revision Library.

This worksheet covers three related strands of the AQA A-Level Computer Science specification. Questions 1 to 6 cover how computers represent numbers: unsigned binary and hexadecimal, two's complement for negative integers, fixed-point binary, and floating-point representation (normalisation, range and precision). Questions 7 to 9 cover how computers represent other kinds of data: characters (ASCII and Unicode), sound (sampling rate and bit depth) and bitmap images (resolution, colour depth and compression). Questions 10 and 11 cover Boolean algebra: the laws used to simplify logic expressions, and deriving a simplified expression directly from a truth table. Questions 12 to 14 cover finite state machines (FSMs) as a model of computation, including tracing, constructing and evaluating them.

Number systems are used throughout computer systems to represent data in different, equivalent forms.

(a)Convert the denary integer 187 to 8-bit unsigned binary, showing your method.(2)

(b)Convert the 8-bit unsigned binary number 01011110 to denary, showing your method.(2)

(c)Convert the 8-bit binary number from part (b), 01011110, to hexadecimal, showing your method (split into nibbles).(2)

(d)Convert the hexadecimal value A9 to an 8-bit binary number, and state its denary value.(2)

(Total for Question 1 is 8 marks)

A microcontroller stores values in an 8-bit unsigned binary register, so it can only hold values from 0 to 255.

(a)Add the two unsigned 8-bit binary numbers 01101011 and 00111001, showing your working column by column (including any carries), and give the 8-bit result.(3)

(b)State, with a reason, whether an overflow has occurred in part (a).(2)

(c)Add the two unsigned 8-bit binary numbers 11001101 and 01101011, showing your working, and state whether overflow occurs this time, explaining your reasoning.(3)

(Total for Question 2 is 8 marks)

An 8-bit register instead stores signed integers using two's complement.

(a)State the range of denary values that can be represented in 8-bit two's complement, and give the two's complement representation of -58, showing your method.(3)

(b)Convert the 8-bit two's complement number 11101010 to denary, showing your method.(2)

(c)Add the two 8-bit two's complement numbers from parts (a) and (b), 11000110 (-58) and 11101010 (-22), showing your binary working. State the 8-bit result, interpret it in denary, and state whether overflow has occurred, giving a reason.(5)

(Total for Question 3 is 10 marks)

An embedded sensor stores fractional readings using an 8-bit fixed-point binary format, with 4 bits for the integer part and 4 bits for the fractional part (format IIII.FFFF, unsigned).

(a)Convert the fixed-point binary number 0101.1100 to denary, showing your method.(2)

(b)Convert the denary value 9.375 to this 8-bit fixed-point binary format (IIII.FFFF), showing your method for both the integer and fractional parts.(3)

(c)State the largest positive denary value that can be represented in this 8-bit format, showing your working. Then explain why increasing the number of fractional bits (keeping the total word length at 8 bits) would improve precision but reduce the range of values that can be represented.(3)

(Total for Question 4 is 8 marks)

A simplified floating-point format uses 12 bits in total: an 8-bit mantissa (1 sign bit followed by 7 fractional bits, with the binary point immediately after the sign bit) and a 4-bit exponent. Both the mantissa and exponent are stored in two's complement, and a floating-point value equals mantissa x 2^exponent.

(a)State what is meant by a normalised floating-point mantissa, and state the condition for a positive mantissa to be normalised in this format.(2)

(b)A floating-point number in this format has mantissa 01010000 and exponent 0011. State whether the mantissa is normalised, explaining your answer, then calculate the denary value represented.(4)

(c)A different floating-point number has mantissa 00010000 and exponent 0101. State whether this mantissa is normalised. If it is not, normalise it (adjusting the exponent accordingly), and show that both the original and the normalised forms represent the same denary value.(4)

(Total for Question 5 is 10 marks)

Question 6 continues to use the 12-bit floating-point format from Question 5 (8-bit mantissa, 4-bit exponent, both two's complement, binary point after the sign bit).

(a)Calculate the maximum positive denary value that can be represented in this format, using a normalised mantissa, showing your working.(3)

(b)A systems designer proposes two changes to this 12-bit format, each keeping the total word length at 14 bits: (i) increasing the mantissa to 10 bits (exponent stays at 4 bits), or (ii) increasing the exponent to 6 bits (mantissa stays at 8 bits). Explain the effect of each change on the precision and the range of numbers that can be represented.(4)

(c)A student claims that floating-point representation can represent any real number exactly, given enough bits. Give one reason why this claim is incorrect.(2)

(Total for Question 6 is 9 marks)

A text file's character encoding is being reviewed for compatibility with different languages.

(a)State the number of bits used to represent one character in 7-bit ASCII, and calculate how many different characters can be represented in this scheme.(2)

(b)A student states that 7-bit ASCII cannot represent the character e with a circumflex (as used in French), or emoji such as a smiley face. Explain why Unicode was developed to address this limitation, and state one advantage Unicode has over extended (8-bit) ASCII.(3)

(c)A document contains 3,200 characters. Calculate the file size, in bytes, needed to store this document using: (i) 7-bit ASCII, with each character stored in a full byte, and (ii) UTF-32 encoding, with each character stored using 32 bits.(3)

(Total for Question 7 is 8 marks)

A recording studio in Manchester is digitising an analogue sound recording.

(a)State what is meant by 'sampling rate' and 'bit depth' when digitising analogue sound.(2)

(b)A recording is sampled at 44,100 Hz with a bit depth of 16 bits, in stereo (2 channels), for a duration of 30 seconds. Calculate the uncompressed file size, in bytes, showing your working.(4)

(c)The engineer wants to increase the audio quality. Explain the effect of increasing the bit depth from 16 bits to 24 bits on (i) the audio quality and (ii) the file size, and state why increasing the sampling rate beyond twice the highest frequency present in the original sound (the Nyquist rate) does not further improve the audio quality that can be perceived.(4)

(Total for Question 8 is 10 marks)

A digital photograph is being prepared for a school website.

(a)State what is meant by 'resolution' and 'colour depth' for a bitmap image.(2)

(b)A bitmap image has a resolution of 1920 x 1080 pixels and a colour depth of 24 bits per pixel. Calculate the file size of this uncompressed image in bytes, and then in megabytes (using 1 MB = 1,048,576 bytes), showing your working.(4)

(c)The image is compressed using a lossy compression algorithm (such as JPEG), resulting in a file of 850 KB (using 1 KB = 1,024 bytes). Calculate the compression ratio achieved (uncompressed size : compressed size), giving your answer to 2 significant figures. State one disadvantage of using lossy compression, rather than lossless compression, for this image.(4)

(Total for Question 9 is 10 marks)

Boolean algebra laws can be used to simplify logic expressions before they are implemented as circuits, reducing the number of gates required.

(a)State the Boolean identity known as De Morgan's first law, and the identity known as De Morgan's second law (for two variables A and B, where ' denotes NOT).(2)

(b)Simplify the Boolean expression X = A.B + A.B' + A'.B, showing each Boolean algebra law you use at each step. Give your final simplified expression.(4)

(c)A different expression is Y = (A+B).(A+B'). Simplify this expression using Boolean algebra laws, showing your working. Confirm your answer by drawing a full truth table for both Y and your simplified expression, for all combinations of A and B.(4)

(Total for Question 10 is 10 marks)

A school's 3D-printer enclosure uses three independent temperature sensors, giving fault signals X, Y and Z (each equal to 1 if that sensor detects an over-temperature fault, 0 otherwise). To avoid a single faulty sensor triggering a false alarm, the enclosure's alarm output A uses majority voting: A = 1 only when at least two of the three sensors (X, Y, Z) report a fault.

(a)Complete the truth table for the alarm output A, for all 8 combinations of X, Y and Z.(3)

(b)Write the Boolean expression for A in sum-of-products (SOP) form, directly from the truth table (one AND term for each row where A=1, combined with OR).(3)

(c)Simplify this Boolean expression using Boolean algebra laws (or otherwise), showing your working, to show that A = X.Y + Y.Z + X.Z.(4)

(Total for Question 11 is 10 marks)

A leisure centre's turnstile is modelled as a finite state machine (FSM) with two states, LOCKED (the start state) and UNLOCKED, and two inputs, COIN (a coin is inserted) and PUSH (someone pushes the turnstile arm). From LOCKED: COIN leads to UNLOCKED; PUSH leaves it in LOCKED (nothing happens). From UNLOCKED: PUSH leads to LOCKED; COIN leaves it in UNLOCKED (a second coin has no further effect).

(a)Complete the state transition table for this FSM, showing the next state for each combination of current state and input.(4)

(b)Starting in the LOCKED state, trace the sequence of states visited for the input string: COIN, PUSH, PUSH, COIN, COIN, PUSH. State the final state reached.(3)

(c)Explain why this FSM is deterministic, in terms of the transitions defined in the transition table.(2)

(Total for Question 12 is 9 marks)

A vending machine's control logic is to be designed as a finite state machine (FSM) that accepts only input strings (sequences of button presses, each either A or B) ending in 'AB', i.e. whose last two symbols, in order, are A followed by B. For example, AB, BAB and AAB should be accepted, but A, B, BA and ABA should not.

(a)Draw a state transition diagram (or an equivalent transition table) for a deterministic finite state machine (DFA) with three states, S0, S1 and S2, that accepts exactly the strings ending in 'AB'. Label the start state, the accepting (final) state, and every transition.(6)

(b)Use your FSM from part (a) to trace the input string BABAB, stating whether it is accepted or rejected, and explaining your reasoning by reference to the states visited.(3)

(c)State one difference between a deterministic finite state machine (DFA) and a non-deterministic finite state machine (NFA), and explain why every NFA can always be converted into an equivalent DFA.(3)

(Total for Question 13 is 12 marks)

A software engineer is deciding whether to model a new lift (elevator) control system as a finite state machine. Discuss the benefits and limitations of using a finite state machine to model a real-world system such as this, and identify one feature of a real lift control system that a simple finite state machine (as used in Questions 12 and 13) might struggle to capture.

(Total for Question 14 is 6 marks)

Mark scheme · A2.9 Data Representation and Theory of Computation

Question 1

(a) M1 correct place values identified and summed, e.g. 128+32+16+8+2+1=187, or an equivalent method (e.g. repeated division by 2) shown
(a) A1 10111011 cao
(a) Answer: 10111011
(b) M1 correct place values applied to each 1 bit, e.g. 64+16+8+4+2
(b) A1 94 cao
(b) Answer: 94
(c) M1 binary correctly split into two 4-bit nibbles: 0101 and 1110
(c) A1 5E cao
(c) Answer: 5E
(d) M1 A correctly converted to 1010 and 9 correctly converted to 1001, giving 10101001
(d) A1 denary value 169 correctly stated (oe, either from the hex or the binary)
(d) Answer: 10101001, denary 169

Question 2

(a) M1 binary addition attempted with carries shown for each column
(a) A1 carries correct throughout (carry sequence, from bit0: 1,1,0,1,1,1,1, final carry out 0)
(a) A1 10100100 cao
(a) Answer: 10100100
(b) B1 no overflow has occurred
(b) B1 correct reason, e.g. there is no carry out of the most significant (bit 7) column, or the true sum 164 fits within the unsigned 8-bit range 0 to 255 (oe)
(b) Answer: No overflow. The final carry out of bit 7 is 0, and the true sum, 164, fits within the unsigned 8-bit range of 0 to 255.
(c) M1 binary addition attempted with carries shown for each column
(c) A1 00111000 correctly given as the 8-bit result (i.e. the final carry out of bit 7 is discarded)
(c) dM1 overflow correctly stated to occur, dependent on a correct or near-correct addition, with correct reason: there is a carry out of the most significant (bit 7) column (a 9th bit is needed), because the true sum, 312, exceeds the maximum unsigned 8-bit value of 255 (oe)
(c) Answer: Result (8-bit): 00111000. Overflow occurs, because the true sum is 205+107=312, which exceeds 255 (the largest value 8 bits can hold), so a carry is generated out of bit 7 that the register cannot store.

Question 3

(a) M1 range correctly stated as -128 to +127 (i.e. -2⁷ to 2⁷-1)
(a) M1 correct method shown, e.g. 58 in binary (00111010), bits inverted (11000101), then 1 added
(a) A1 11000110 cao
(a) Answer: Range: -128 to +127. -58 = 11000110.
(b) M1 correct place values applied, with the most significant bit given a negative weight (-128)
(b) A1 -22 cao
(b) Answer: -22
(c) M1 binary addition attempted with carries shown for each column
(c) A1 10110000 correctly given as the 8-bit result
(c) B1 correctly interpreted as -80 in denary (ft from their binary result)
(c) B1 no overflow correctly stated
(c) B1 correct reason: the carry into the most significant (sign) bit equals the carry out of it (both 1 here), or equivalently the true sum, -80, lies within the representable range of -128 to +127 (oe)
(c) Answer: Result: 10110000, which represents -80. No overflow, since the carry into bit 7 and the carry out of bit 7 are both 1 (equal), and -80 is within the representable range.

Question 4

(a) M1 integer part correctly identified as 5, and fractional part correctly weighted (1/2 + 1/4 = 0.75)
(a) A1 5.75 cao
(a) Answer: 5.75
(b) B1 integer part correctly converted: 9 = 1001
(b) B1 fractional part correctly converted using repeated doubling: 0.375 = 0110 (0.375x2=0.75 -> 0, 0.75x2=1.5 -> 1, 0.5x2=1.0 -> 1, 0x2=0 -> 0)
(b) B1 1001.0110 correctly combined cao
(b) Answer: 1001.0110
(c) B1 correct largest value 15.9375, with working shown (integer part 1111=15, fractional part 1111=15/16=0.9375)
(c) B1 precision correctly explained: more fractional bits give a smaller gap between adjacent representable values, i.e. finer resolution (oe)
(c) B1 range correctly explained: with a fixed 8-bit word length, giving more bits to the fractional part leaves fewer bits for the integer part, reducing the largest (and smallest) value that can be represented (oe)
(c) Answer: Largest value: 15.9375 (integer part 1111=15, fractional part 1111=15/16=0.9375). More fractional bits improve precision (smaller gaps between representable values) but, because the total word length is fixed, this takes bits away from the integer part, reducing the overall range.

Question 5

(a) B1 normalisation adjusts the mantissa and exponent so that the mantissa uses the maximum number of significant bits available, maximising the precision of the representation, with a single, unique representation for each value (oe)
(a) B1 for a positive mantissa, the condition is that the sign bit is 0 and the first bit after the binary point is 1 (i.e. the sign bit and the following bit differ)
(a) Answer: Normalisation adjusts the mantissa (and exponent) so it uses the maximum number of significant bits, maximising precision. For a positive mantissa, it is normalised when the sign bit is 0 and the very next bit (the first bit after the binary point) is 1.
(b) B1 correctly states the mantissa is normalised, because the sign bit (0) and the first fractional bit (1) differ
(b) B1 mantissa correctly evaluated as 0.625 (0.1010000 = 1/2 + 1/8), with method shown
(b) B1 exponent correctly evaluated as +3 (0011 in 4-bit two's complement)
(b) B1 5 correctly calculated as the final value (0.625 x 2³ = 0.625 x 8), ft from their mantissa/exponent
(b) Answer: Normalised (sign bit 0, next bit 1, so they differ). Mantissa = 0.625, exponent = +3. Value = 0.625 x 2³ = 5.
(c) B1 correctly states the mantissa is NOT normalised, because the sign bit (0) and the first fractional bit (0) are the same
(c) B1 correct normalisation method: shift the mantissa left (multiply by 2) and decrease the exponent by 1, repeated until the first fractional bit differs from the sign bit
(c) B1 correct normalised form: mantissa 01000000, exponent 0011 (i.e. two left shifts, exponent reduced by 2 from 5 to 3)
(c) B1 correctly shows both forms give the same value: original 0.0010000 x 2⁵ = 0.125 x 32 = 4, and normalised 0.1000000 x 2³ = 0.5 x 8 = 4
(c) Answer: Not normalised. Normalised form: mantissa 01000000, exponent 0011. Both the original (0.125 x 2⁵) and the normalised form (0.5 x 2³) equal 4.

Question 6

(a) B1 maximum normalised positive mantissa correctly found as 0.9921875 (0.1111111 = 1 - 2^-7 = 127/128), with method shown
(a) B1 maximum exponent correctly found as +7 (0111 in 4-bit two's complement)
(a) B1 127 correctly calculated as the final maximum value (0.9921875 x 2⁷ = (127/128) x 128) cao
(a) Answer: 127
(b) B1 (i) precision increases, because more mantissa bits give a smaller gap between adjacent representable values (finer resolution) (oe)
(b) B1 (i) range is unaffected, because the exponent (which determines the scale/magnitude of numbers) is unchanged (oe)
(b) B1 (ii) range increases, because more exponent bits allow both larger maximum and smaller minimum magnitudes to be represented (oe)
(b) B1 (ii) precision is unaffected, because the mantissa (which determines the number of significant bits/digits) is unchanged (oe)
(b) Answer: (i) Increases precision (smaller gaps between values); range stays the same, since the exponent is unchanged. (ii) Increases range (larger maximum and smaller minimum magnitude); precision stays the same, since the mantissa is unchanged.
(c) B1 valid reason identified, e.g. some numbers (irrational numbers such as π or √2, or recurring binary fractions such as 0.1 in decimal) require an infinite number of digits/bits to represent exactly, however many bits are used (oe)
(c) B1 developed to floating point specifically: since the mantissa always has a fixed, finite number of bits, such values must be rounded/truncated, introducing a small representation (rounding) error (oe)
(c) Answer: Some real numbers (e.g. irrational numbers, or recurring binary fractions) need an infinite number of bits to represent exactly. Since any floating-point format has a fixed, finite number of mantissa bits, such values must be rounded, introducing a small error, however many bits are used.

Question 7

(a) B1 7 bits stated
(a) B1 128 correctly calculated (2⁷) cao
(a) Answer: 7 bits; 2⁷ = 128 characters.
(b) B1 explains why ASCII is limited: 7-bit ASCII only encodes 128 characters, mostly basic Latin letters, digits and control characters, so it has no code points for accented letters, other scripts (e.g. Chinese, Arabic, Cyrillic) or symbols such as emoji (oe)
(b) B1 describes what Unicode does: it gives every character, in every writing system (and many symbols), a unique code point, so text in any language or script can be represented consistently (oe)
(b) B1 valid stated advantage over extended ASCII, e.g. Unicode supports a vastly larger number of characters (extended ASCII is limited to 256), allowing many different languages/scripts to be mixed reliably in the same document (oe)
(b) Answer: 7-bit ASCII only has 128 code points, covering basic Latin characters, so it cannot represent accented letters, other scripts, or symbols like emoji. Unicode gives every character in every script (and many symbols) a unique code point. Advantage: Unicode supports far more than the 256 characters of extended ASCII, so many languages can be represented consistently in one standard.
(c) M1 correct method: number of characters x bytes per character, for each scheme (1 byte for (i), 4 bytes for (ii))
(c) A1 (i) 3200 bytes cao
(c) A1 (ii) 12800 bytes cao
(c) Answer: (i) 3200 x 1 = 3,200 bytes. (ii) 3200 x 4 = 12,800 bytes.

Question 8

(a) B1 sampling rate: the number of samples of the sound wave's amplitude taken per second, measured in Hz (oe)
(a) B1 bit depth: the number of bits used to store each sample's amplitude value, which determines how many distinct amplitude levels can be represented (oe)
(a) Answer: Sampling rate: the number of amplitude samples taken per second, measured in Hz. Bit depth: the number of bits used to store each sample, which determines how many distinct amplitude levels are possible.
(b) M1 correct method identified: sampling rate x bit depth x number of channels x duration
(b) M1 correct bit calculation: 44100 x 16 x 2 x 30 = 42,336,000 bits
(b) A1 correct conversion from bits to bytes (divide by 8)
(b) A1 5,292,000 bytes cao
(b) Answer: 5,292,000 bytes
(c) B1 (i) increasing bit depth increases the number of distinct amplitude levels per sample (2²⁴ vs 2¹⁶), reducing quantisation error, so the digital recording represents the original amplitude more accurately (oe)
(c) B1 (ii) file size increases proportionally, since bit depth is a direct multiplier in the file size calculation (e.g. by a factor of 24/16 = 1.5, all else unchanged) (oe)
(c) B1 the sampling theorem states that sampling at (at least) twice the highest frequency present is sufficient to capture all the frequency information in the original analogue signal without loss (oe)
(c) B1 once the sampling rate already exceeds this Nyquist rate, there is no additional frequency information left to capture, so sampling faster only increases file size/processing without improving perceived quality (oe)
(c) Answer: (i) Higher bit depth gives more possible amplitude levels, reducing quantisation error and improving quality. (ii) File size increases proportionally (by 1.5x here). Once the sampling rate exceeds twice the highest frequency present (the Nyquist rate), all the frequency information is already captured, so sampling even faster adds no further perceivable quality, only extra file size.

Question 9

(a) B1 resolution: the number of pixels that make up the image, usually given as width x height (oe)
(a) B1 colour depth: the number of bits used to represent the colour of each pixel, which determines how many distinct colours can be represented (oe)
(a) Answer: Resolution: the number of pixels in the image (width x height). Colour depth: the number of bits used to represent each pixel's colour, which determines how many distinct colours are possible.
(b) M1 correct total pixel count: 1920 x 1080 = 2,073,600
(b) M1 correct bit calculation: 2,073,600 x 24 = 49,766,400 bits
(b) A1 correct byte conversion: 49,766,400 / 8 = 6,220,800 bytes
(b) A1 correct MB conversion: 6,220,800 / 1,048,576, awrt 5.93 MB
(b) Answer: 6,220,800 bytes, which is approximately 5.93 MB.
(c) M1 compressed size correctly converted to bytes: 850 x 1024 = 870,400 bytes
(c) M1 correct method: uncompressed bytes / compressed bytes
(c) A1 awrt 7.1 (accept 7.1 : 1 or equivalent), ft from part (b)'s uncompressed size
(c) B1 valid disadvantage of lossy compression, e.g. it permanently discards some image data/detail to shrink the file, so quality is reduced and the discarded data cannot be recovered, unlike lossless compression (oe)
(c) Answer: Compressed size = 850 x 1024 = 870,400 bytes. Ratio = 6,220,800 / 870,400 = awrt 7.1 (i.e. about 7.1:1). Disadvantage: lossy compression permanently discards some image data, reducing quality in a way that cannot be undone, unlike lossless compression.

Question 10

(a) B1 first law: (A.B)' = A' + B'
(a) B1 second law: (A+B)' = A'.B'
(a) Answer: (A.B)' = A' + B'. (A+B)' = A'.B'.
(b) M1 distributive law correctly applied to the first two terms: A.B + A.B' = A.(B+B')
(b) M1 complement law and identity law correctly applied: B+B'=1, so A.(B+B') = A.1 = A, giving X = A + A'.B
(b) M1 absorption identity correctly applied: A + A'.B = A + B
(b) A1 X = A + B cao, fully simplified
(b) Answer: X = A + B
(c) M1 distributive law correctly applied in the form (A+B).(A+C) = A + B.C, giving Y = A + B.B'
(c) M1 complement law and identity law correctly applied: B.B'=0, so Y = A+0 = A
(c) A1 correct truth table with all 4 rows correctly evaluated for both Y and A
(c) B1 correct concluding statement that the Y column and the A column match in every row, confirming Y = A
(c) Answer: Y = A. Truth table: A=0,B=0: Y=(0)(1)=0, A=0 (match). A=0,B=1: Y=(1)(0)=0, A=0 (match). A=1,B=0: Y=(1)(1)=1, A=1 (match). A=1,B=1: Y=(1)(1)=1, A=1 (match).

Question 11

(a) B1 A=0 correctly given for every row with zero or exactly one fault signal set to 1 (rows 000, 001, 010, 100)
(a) B1 A=1 correctly given for every row with exactly two fault signals set to 1 (rows 011, 101, 110)
(a) B1 A=1 correctly given for the row with all three fault signals set to 1 (row 111)
(a) Answer:
X Y Z A
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
(b) B1 the four rows where A=1 correctly identified: (0,1,1), (1,0,1), (1,1,0), (1,1,1)
(b) B1 each row correctly written as an AND term with correct complementation, e.g. X'.Y.Z for (0,1,1)
(b) B1 all four terms correctly combined with OR: A = X'.Y.Z + X.Y'.Z + X.Y.Z' + X.Y.Z
(b) Answer: A = X'.Y.Z + X.Y'.Z + X.Y.Z' + X.Y.Z
(c) M1 recognises the idempotent law (X.Y.Z = X.Y.Z + X.Y.Z + X.Y.Z), allowing X.Y.Z to be paired with each of the other three terms
(c) M1 each pair correctly factorised using the distributive law, e.g. X'.Y.Z + X.Y.Z = Y.Z.(X'+X)
(c) M1 complement law and identity law correctly applied to each pair, e.g. X'+X=1, so Y.Z.(X'+X) = Y.Z
(c) A1 A = X.Y + Y.Z + X.Z correctly given as the final simplified expression cao
(c) Answer: A = X.Y + Y.Z + X.Z

X Y Z	A
0 0 0	0
0 0 1	0
0 1 0	0
0 1 1	1
1 0 0	0
1 0 1	1
1 1 0	1
1 1 1	1

Question 12

(a) B1 LOCKED, COIN -> UNLOCKED
(a) B1 LOCKED, PUSH -> LOCKED
(a) B1 UNLOCKED, COIN -> UNLOCKED
(a) B1 UNLOCKED, PUSH -> LOCKED
(a) Answer:
Current State Input Next State
LOCKED COIN UNLOCKED
LOCKED PUSH LOCKED
UNLOCKED COIN UNLOCKED
UNLOCKED PUSH LOCKED
(b) M1 correct states after the first three inputs: UNLOCKED, LOCKED, LOCKED
(b) M1 correct states after the last three inputs: UNLOCKED, UNLOCKED, LOCKED
(b) A1 final state correctly stated as LOCKED cao
(b) Answer: States visited: UNLOCKED, LOCKED, LOCKED, UNLOCKED, UNLOCKED, LOCKED. Final state: LOCKED.
(c) B1 a deterministic FSM has exactly one transition (to exactly one next state) defined for every state and input combination (oe)
(c) B1 correctly applies this to the table: both states (LOCKED, UNLOCKED) have exactly one next state defined for each of the two inputs (COIN, PUSH), so there is never any ambiguity about which state to move to
(c) Answer: A deterministic FSM has exactly one defined next state for every state/input combination. Here, both LOCKED and UNLOCKED each have exactly one next state for COIN and one for PUSH, so at every step there is never a choice between more than one possible next state.

Current State	Input	Next State
LOCKED	COIN	UNLOCKED
LOCKED	PUSH	LOCKED
UNLOCKED	COIN	UNLOCKED
UNLOCKED	PUSH	LOCKED

Question 13

(a) B1 S0 correctly labelled as the start state
(a) B1 S2 correctly labelled as the only accepting/final state
(a) B1 correct transitions from S0: A -> S1, B -> S0
(a) B1 correct transitions from S1: A -> S1, B -> S2
(a) B1 correct transitions from S2: A -> S1, B -> S0
(a) B1 every state has exactly one transition defined for each input (confirming a valid, complete DFA)
(a) Answer: Transition table (equivalent to the diagram): S0 (start), on A -> S1, on B -> S0. S1, on A -> S1, on B -> S2 (accepting). S2 (accepting, final), on A -> S1, on B -> S0.
(b) M1 correct sequence of states shown: S0, S0, S1, S2, S1, S2
(b) A1 correctly concludes ACCEPTED, ft from their FSM in part (a)
(b) B1 correct reasoning: the final state reached, S2, is the accepting state, because the last two symbols of BABAB are A then B
(b) Answer: S0 -B-> S0 -A-> S1 -B-> S2 -A-> S1 -B-> S2. Accepted, since the final state, S2, is the accepting state (the string ends in AB).
(c) B1 correct difference: in a DFA every state has exactly one transition defined for each input symbol, whereas in an NFA a state may have zero, more than one, or empty (epsilon) transitions for the same input (oe)
(c) B1 correctly states that NFAs and DFAs are equivalent in what they can recognise, i.e. they recognise exactly the same class of languages (regular languages) (oe)
(c) B1 correctly references a conversion method, e.g. the subset construction, which builds a DFA whose states represent sets of NFA states that could be reached simultaneously (oe)
(c) Answer: DFA: exactly one transition per state per input. NFA: can have zero, more than one, or epsilon transitions per state per input. Every NFA can be converted to an equivalent DFA (they recognise the same class of languages) using a method such as the subset construction, where each DFA state represents a set of possible NFA states.

Question 14

Level 3 (5-6): A clear, well-developed discussion identifies at least one accurate benefit and one accurate limitation of FSM modelling, with specific, correct reference to a feature of a lift control system an FSM would struggle to capture.
Level 2 (3-4): Some accurate benefit(s) and/or limitation(s) are given, but the discussion is less developed or the link to the lift example is generic or limited.
Level 1 (1-2): A basic, undeveloped statement about FSMs is made, with little or no application to the lift example.
Level 0 (0): No creditable content.
Indicative content:
- Benefit: an FSM gives a precise, unambiguous model of every state the system can be in and every transition between them, which can be systematically checked for completeness (e.g. every state has a defined transition for every input) and used to design and test the control logic methodically.
- Benefit: because an FSM has a strictly finite number of states, its behaviour is fully predictable and can, in principle, be exhaustively traced or tested, which is valuable for a safety-critical control system such as a lift.
- Limitation: an FSM's number of states is fixed and finite; if a system needs to remember or count an arbitrarily large or varying amount of information, rather than simply being in one of a small number of states, this either cannot be modelled exactly by a small FSM, or requires an impractically large number of states.
- Applied to the lift: a lift may need to service several floor requests queued at once (e.g. requests from several different floors pending together) and decide an efficient order to visit them; a simple FSM state only records where the lift currently is or what it is currently doing, not the full combination of which floors currently have outstanding requests, so modelling every possible combination of pending requests would need a separate state for every combination, which does not scale well as the number of floors increases.
- Valid overall conclusion: FSMs remain a useful model for the lift's basic modes (e.g. moving up, moving down, idle, doors open) but a full lift controller in practice usually needs extra memory or logic beyond a pure FSM to track multiple pending requests.

Data Representation and Theory of Computation - Worksheets, Questions and Revision