Data Representation and Theory of Computation
Data representation and theory of computation covers two related theoretical foundations. The first is how computers represent text, building on earlier binary number work with character sets such as ASCII and Unicode (commonly encoded as UTF-8), plus the range/precision trade-off in floating point representation. The second is the abstract models computer scientists use to reason about computation itself: finite state machines, regular expressions and Turing machines, and computability, meaning which problems can and cannot be solved by any algorithm at all, illustrated by the halting problem. This second half is examined as part of computational thinking and algorithms.
Before you start
Make sure you're comfortable with these topics first:
Method
- Recall that all data, including negative numbers via two's complement and real numbers via a normalised mantissa and exponent, is ultimately stored as binary patterns, then extend this to how text and symbols are represented.
- Distinguish ASCII, a fixed 7-bit code giving 128 characters stored one byte each, from Unicode, a much larger set of code points intended to cover every written language; recall that UTF-8 stores each Unicode code point using between 1 and 4 bytes, and stays backward compatible with ASCII for the first 128 code points.
- Reason about the range/precision trade-off in a floating point representation: for a fixed total number of bits, allocating more bits to the exponent widens the range of representable magnitudes, while allocating more bits to the mantissa improves precision.
- For a finite state machine (FSM) question, identify the states, the start state, any accepting (final) states, and the transition for every state/input pair, then trace the given input string one symbol at a time to find which state the machine finishes in.
- For a regular expression question, break an unfamiliar pattern into its parts (a literal character, alternation using the OR symbol |, and repetition using *) and test it symbol by symbol against example strings, or build a new expression up from the requirements the question describes.
- For a Turing machine question, focus on what its read/write head, tape and transition rules are doing at each step, reading the current symbol, writing a symbol, moving left or right and changing state, rather than trying to recall one fixed worked answer.
- For a computability question, decide whether the problem describes something an algorithm can always solve correctly (decidable) or a problem, like the halting problem, that has been proven impossible for any algorithm to solve correctly for every possible case (undecidable).
Worked example
A text file contains the string 'CAT' followed by a single Euro sign character (Unicode code point U+20AC). Standard ASCII characters are stored using 1 byte each in UTF-8, and the Euro sign requires 3 bytes in UTF-8. Calculate the total file size in bytes for this string, ignoring any file header.
- Identify that 'CAT' consists of 3 characters, each within the basic ASCII range, so each takes 1 byte in UTF-8: 3 x 1 = 3 bytes.
- Identify that the Euro sign (U+20AC) falls outside the ASCII range, so UTF-8 encodes it using 3 bytes, as given.
- Add the two parts together: 3 bytes (for CAT) + 3 bytes (for the Euro sign).
- Calculate the result: 3 + 3 = 6.
- Final answer: the string requires 6 bytes in total when stored using UTF-8.
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1State one advantage of Unicode over ASCII for representing text.Show answer
Answer: Unicode can represent characters from many different languages and scripts (and symbols) using one consistent standard, whereas ASCII, with only 128 characters, can represent only basic unaccented English letters, digits and a few symbols.
Q2State how many bytes UTF-8 uses to store a standard ASCII character, such as the letter 'A'.Show answer
Answer: 1 byte, because UTF-8 is designed to be backward compatible with 7-bit ASCII, so every ASCII character is stored using a single byte.
Q3A floating point number is stored using a fixed total of 16 bits, split between the mantissa and the exponent. Explain the effect on the number's precision and range if more of those 16 bits are allocated to the exponent and fewer to the mantissa.Show answer
Answer: More exponent bits increases the range of values that can be represented, since larger positive and negative powers of 2 become possible, but it leaves fewer bits for the mantissa, which reduces precision: fewer significant bits means more numbers must be rounded to the nearest representable value, increasing rounding error.
Q4State three things that must be defined to fully specify a finite state machine.Show answer
Answer: Its states (including which one is the start state and which, if any, are accepting states), the input alphabet (the set of symbols it can read), and the transitions between states for each state/input pair.
Q5Write a regular expression that matches only the strings 'cat' and 'cot', and no other strings.Show answer
Answer: c(a|o)t
Q6A finite state machine has start state S0 and accepting state S2, with transitions S0 -> S1 on input 'a', S1 -> S1 on input 'a', S1 -> S2 on input 'b', and S2 -> S2 on input 'b'. State whether the input string 'aab' is accepted, showing the sequence of states visited.Show answer
Answer: Accepted. The sequence of states visited is S0, S1, S1, S2: S0 to S1 on the first 'a', S1 to S1 on the second 'a', then S1 to S2 on 'b', finishing on the accepting state S2.
Q7State what is meant by an 'undecidable problem', and name one example.Show answer
Answer: A problem for which it can be proven that no algorithm exists that always halts and gives a correct yes/no answer for every possible input. One example is the halting problem: deciding, for an arbitrary program and its input, whether that program will eventually halt or run forever.
Q8State what is stored on a Turing machine's tape, and state what determines which single symbol its read/write head examines at any point.Show answer
Answer: The tape stores a sequence of symbols from a finite alphabet, and is treated as being of unlimited length (blank beyond the part already used). The head examines whichever one cell of the tape it is currently positioned over, and that position changes only when a transition rule moves the head one cell left or right.
Exam-style questions
Written in the style of a A Level Computer Science exam paper, with a full mark scheme.
A short message consists of 10 ASCII characters and 2 Chinese characters. Each ASCII character is stored using 1 byte in UTF-8, and each Chinese character requires 3 bytes in UTF-8. Calculate the total number of bytes needed to store this message.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
A Turing machine's tape initially contains the binary number 1011 followed by blank cells, with the read/write head positioned on the leftmost symbol. Explain how a Turing machine could use its read/write head, states and transition rules to determine whether this binary number is even or odd, and state the final answer for 1011.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
Discuss the statement 'any problem that can be described precisely can be solved by a computer program', with reference to the halting problem and the idea of an undecidable problem.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 9 available
See real A Level Computer Science past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the data representation and theory of computation worksheet pack - 13 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on data representation and theory of computation, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.