Regular Expressions and Regular Languages

Concatenation places patterns in sequence. Alternation, written |, permits either alternative. Parentheses group a subexpression. A star permits zero or more repetitions, a plus one or more, and a question mark zero or one occurrence of the preceding expression.

The pattern a(b|c)* describes a followed by any finite sequence of b and c symbols, including no such symbols. It accepts a, ab and acbc, but not an empty string or ba. The star applies to the grouped alternative, not to the initial a.

A regular language is one that can be described by a formal regular expression and equivalently accepted by a finite state machine. These are two representations of the same language class: a compact symbolic rule and a state-based input processor.

For binary strings ending in 1, (0|1)*1 permits any binary prefix and then a final 1. An FSM need only remember whether the most recently read symbol was 1. A regular expression is not a rule for generating only one example; it specifies the complete accepted set.

A programming library may search for a matching substring by default. Whole-string language recognition instead requires every input symbol to fit the pattern. Python re.fullmatch expresses that distinction without requiring students to memorise extra anchor syntax.

Real regex engines may contain extensions beyond formal regular expressions, including features whose theoretical power differs. AQA’s core metacharacters are the stated repetition, grouping and alternation operators; other notation used in a question should be explained. Test the empty string, shortest valid input and close invalid neighbours.

import re
pattern = r"a(b|c)*"
for text in ["a", "abcb", "ba", ""]:
    print(text, bool(re.fullmatch(pattern, text)))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.