FSMs, regular expressions and BNF – A-level Computer Science exam questions with mark scheme

1Core4 marks

The finite state machine (FSM) below has start state A and accepting state C. The input alphabet is {0, 1}.

(a) State whether the input 10101 is accepted. Justify your answer. [1]

(b) State whether the input 0110 is accepted. Justify your answer. [1]

(d) Write a regular expression that defines the same language as this FSM. [1]

(a) Accepted – path A, A, B, C, B, C ends in the accepting state C (both the decision and the final state/path needed)(1)
(b) Not accepted – path A, B, C, A, B ends in state B, which is not an accepting state (both the decision and the final state/path needed)(1)
(c) All strings (of 0s and 1s) that end in 01; NE 'strings containing 01'(1)
(d) (0|1)*01; accept any equivalent expression that matches exactly the strings ending in 01, e.g. (1|0)*01(1)
Answer: (a) Accepted (ends in C) (b) Rejected (ends in B) (c) Strings ending in 01 (d) (0|1)*01
Examiner tip: Always finish the trace and check whether the LAST state is accepting; passing through C earlier does not count.

2Standard4 marks

A regular expression is a(b|c)*d.

(a) The strings below are tested against the whole regular expression. Identify which strings match.

ad abcd abbcb acbbd abdd aabd [2]

(b) Write a regular expression for the set of all strings of 0s and 1s that start with 1 and end with 0. [2]

(a) Correctly identifies matches: ad, abcd, acbbd (at least two of the three correct with no incorrect strings)(1)
(a) All three matching strings and no others(1)
(b) 1 at the start and 0 at the end(1)
(b) (0|1)* between them to allow any number of 0s and 1s, i.e. 1(0|1)*0(1)
Answer: (a) ad, abcd, acbbd (b) 1(0|1)*0
Examiner tip: In (b) the string must be at least two symbols long (1 then 0), and the * allows zero or more middle symbols.

3Standard5 marks

A number format is defined using Backus-Naur Form (BNF):

<digit> ::= 0|1|2|3|4|5|6|7|8|9
<unsigned> ::= <digit> | <digit><unsigned>
<number> ::= <unsigned> | +<unsigned> | -<unsigned>

(a) State which of these are valid <number>s: -07 +-5 5- 42 [2]

(b) Explain how the definition of <unsigned> allows numbers of any length. [1]

(c) Write BNF rules for a <name> that must start with a letter followed by any number of letters or digits. You may assume <letter> and <digit> are already defined. [2]

(a) -07 identified as valid(1)
(a) 42 identified as valid; deduct 1 mark for each invalid string (+-5 or 5-) also given as valid (minimum 0 for part (a))(1)
(b) <unsigned> is defined in terms of itself (recursion), so another digit can be added any number of times(1)
(c) <name> ::= <letter> | <letter><rest> (starts with a letter, optionally followed by more); allow an equivalent left-recursive form such as <name> ::= <letter> | <name><letter> | <name><digit> for both (c) marks(1)
(c) <rest> ::= <letter> | <digit> | <letter><rest> | <digit><rest> (recursive rule for any mix of letters and digits); accept any equivalent rules, e.g. <char> ::= <letter> | <digit> and <rest> ::= <char> | <char><rest>(1)
Answer: (a) -07, 42 (b) Recursive rule (c) <name> ::= <letter> | <letter><rest>; <rest> ::= <letter>|<digit>|<letter><rest>|<digit><rest>
Examiner tip: BNF has no * or loops: repetition can only be achieved by a rule that refers to itself.

Stuck on FSMs, regular expressions and BNF?

Get it sorted in a free 30-minute session

We work through your weakest questions on this topic on Zoom. I reply the same day.

Free 30-min session on this topic Send me 5 questions a day

4Hard5 marks

The FSM below has start state A, which is also the only accepting state. The input alphabet is {0, 1}.

(a) State whether each input is accepted: 1001 and 0111. [2]

(b) Write a regular expression for the strings accepted by the FSM. [2]

(c) Explain why an FSM cannot be used to recognise the language of strings with n 0s followed by exactly n 1s for any n. [1]

(a) 1001 accepted (two 1s, finishes in A)(1)
(a) 0111 not accepted (three 1s, finishes in B)(1)
(b) Correct pattern for a pair of 1s with any number of 0s between them, e.g. 10*1(1)
(b) Fully correct expression that also allows 0s before/after and any number of pairs (including none), e.g. 0*(10*10*)* or (0|10*1)*; accept any equivalent expression that matches exactly the strings with an even number of 1s(1)
(c) An FSM has a fixed, finite number of states (no other memory), so it cannot remember/count an unbounded number of 0s to match against the 1s(1)
Answer: (a) 1001 accepted, 0111 rejected (b) 0*(10*10*)* (or equivalent, e.g. (0|10*1)*) (c) Finite memory cannot count unlimited 0s
Examiner tip: Describe the language first (an even number of 1s) and then build the regex from it.

Stuck on this topic?

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.

Free 30-minute session