Regular Expressions & Regular Languages | AQA A Level Computer Science 7517 | 20 Worksheets + Answer

Regular expressions for AQA A Level Computer Science (7517): twenty different
expressions, each worked all the way through, and each with a complete answer
key.

Section 4.4.2.3 asks candidates to form and use simple regular expressions,
and to write a regular expression that recognises the same language as a given
finite state machine AND THE OTHER WAY ROUND. Most resources only go one way.
Every sheet here goes both.

WHAT YOU GET

• 20 worksheets, 3 pages each, numbered 01 to 20
• 20 matching answer keys
• A contents table giving each sheet’s expression and its written question, so
  you can pick one without opening all twenty

WHAT IS ON EVERY SHEET

Question 1 prints an expression and six strings. For each string, does the
expression describe it? One of the six is chosen so that the answer turns on
the rule the whole topic argues about.

Question 2 gives a finite state machine and asks for a regular expression that
describes exactly what it accepts, the shortest string it accepts, and how
many strings of length four it accepts.

Question 3 goes the other way. It prints an expression and three machines,
only one of which accepts exactly what the expression describes. For each of
the other two, the student writes the shortest string on which the machine and
the expression disagree - and there is exactly one such string in each case.

Question 4 is set notation: membership, union, intersection, difference,
cardinality, and the compact form the specification itself writes.

Question 5 is a written question on the equivalence of expressions and
machines, on what makes a language regular, on the difference between * and +,
on an expression as a set, or on whole-string matching.

Every sheet is 30 marks.