Skip to topic
    ← Back to course topics

    Regular language — AQA A-Level Computer Science

    A regular language is any formal language that can be accepted by a finite state machine (FSM) or described using a regular expression. In AQA A-Level Computer Science, regular languages form the foundation of formal language theory and represent the simplest class in the Chomsky hierarchy.

    Regular language explained

    A formal language is the set of strings built from a given alphabet that satisfy some rule.

    Read the full explanation

    In this topic, a language is called regular when a regular expression can describe exactly the strings in that set. A regular expression is a compact pattern built from symbols of the alphabet using concatenation (writing symbols one after another), alternation (choice, written as a vertical bar), and repetition (the Kleene star, meaning zero or more copies). For example, the expression (a|b)*ab describes every string of a's and b's that ends in ab. Recognising this statement means understanding that the existence of such an expression is what makes the language regular. You should be able to read a simple regular expression, state which strings it matches, and recognise a language described in words that can be written as one.

    Your focus

    1. Know that a language is called regular if it can be represented by a regular expression.

    Which command word is this?

    Give a concise regular expression or name a specific state without narrative explanation or working.

    Regular language exam tips

    Topic Overview

    A regular language is a formal language that can be fully defined by a regular expression and recognised by a finite state machine (either deterministic or non-deterministic). In AQA A-Level Computer Science, regular languages form the lowest tier of the Chomsky hierarchy of languages, demonstrating the computational limits of systems with finite, fixed memory.

    Understanding regular languages is essential for practical computer science applications such as lexical analysis in compilers, input validation, and text search algorithms. Mastery of this topic connects theoretical computation concepts like state transitions and formal grammars to real-world software tooling.

    Key Concepts
    • →Equivalence: Any language definable by a regular expression can also be recognised by a finite state machine, and vice versa.
    • →Operations: Regular languages are closed under union (| or +), concatenation, and Kleene star (*) repetition.
    • →Finite Memory: A finite state machine has no auxiliary memory (such as a stack or tape); it can only retain a fixed, finite number of states.
    • →Limitations: Regular languages cannot recognise languages requiring unbounded counting or arbitrarily nested structures, such as balanced parentheses.
    Marking Points
    • Identifies that a regular language is one for which a regular expression exists that matches exactly its strings.
    • Explains that a regular expression is built from symbols using concatenation, alternation and repetition.
    • Interprets a given regular expression correctly, listing or describing the strings it matches.
    • Recognises that the test is whether a regular expression can describe the language, not whether the language is simple.
    Examiner Tips
    • 💡Read each option as a pattern and test one or two example strings against it.
    • 💡Check whether the empty string is matched when a star appears in the expression.
    • 💡Eliminate options that describe a different alphabet or ignore a required symbol.
    • 💡When drawing state transition diagrams, always explicitly mark the start state with an incoming arrow and all accepting states with double circles.
    • 💡Check whether the empty string (epsilon) should be accepted by your regular expression or machine, as missing the zero-occurrence edge case is a frequent error.
    • 💡Use standard AQA regular expression notation: use '|' or '+' for OR depending on paper specification, and always use parentheses to make operator precedence explicit.
    Common Mistakes
    • Assumes a language is regular only when it is short or finite; a regular language can be infinite, such as strings of any length of a's. Correct by checking whether a regular expression can describe the set, not its size.
    • Treats the Kleene star as meaning exactly one copy; it means zero or more copies. Correct by checking that the empty string is included when a star is applied.
    • Confuses the vertical bar with a logical OR inside strings; it is alternation between patterns. Correct by reading it as 'either this pattern or that pattern'.
    • Believing that regular expressions can parse recursive syntax like HTML or mathematical expressions with arbitrary nesting; these require context-free grammars.
    • Confusing the Kleene plus (+) operator with the Kleene star (*); '+' requires at least one occurrence, whereas '*' permits zero occurrences.
    • Assuming non-deterministic finite state machines (NFAs) can recognise languages that deterministic finite state machines (DFAs) cannot; both recognise exactly the same class of regular languages.
    Revision Plan
    1. 1Day 1-2: Review regular expression syntax (concatenation, alternation, Kleene star, and Kleene plus) and practice writing expressions for simple patterns.
    2. 2Day 3-4: Practice converting regular expressions into equivalent Deterministic Finite State Machine (DFA) transition state diagrams.
    3. 3Day 5-6: Solve past AQA exam questions distinguishing regular languages from non-regular languages, focusing on memory constraints.
    4. 4Day 7: Complete timed active recall tests and draw state transition tables without reference materials.
    Exam Question Types
    • 📋Expression to Machine: Given a regular expression, draw the corresponding finite state transition diagram or complete a transition table.
    • 📋Machine to Expression: Inspect an FSM diagram and write the minimal or standard regular expression that defines the accepted language.
    • 📋Theoretical Classification: Explain why a given language is or is not regular with reference to finite state memory limitations.
    Command Word Expectations (AQA)
    State

    Give a concise regular expression or name a specific state without narrative explanation or working.

    Explain

    Set out the mathematical or logical reasoning clearly, linking the inability of an FSM to store unbounded counts directly to why a language is non-regular.

    Draw

    Produce a clear state transition diagram showing all states, directed transition arrows labelled with inputs, a start arrow, and double circles for accepting states.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing the empty string with the empty set, or failing to realise that the Kleene star operation includes zero occurrences (the empty string).
    ❌ Weak Answer (Loses Marks):The expression a*b means any number of a followed by b, so strings like aaab or ab work, but not just b.
    Example improved answer:The Kleene star (*) denotes zero or more repetitions of the preceding symbol. Therefore, a*b matches any sequence starting with zero or more 'a' characters followed strictly by a single 'b', meaning 'b' alone is a valid accepted string.
    Examiner Tip: Always test the boundary condition of zero occurrences (the empty string) whenever you see a Kleene star in regular expressions or transition loops in finite state machines.
    Pitfall: Assuming finite state machines can count arbitrary matched pairs (e.g. matching an equal number of opening and closing brackets).
    ❌ Weak Answer (Loses Marks):A finite state machine can recognise L = {a^n b^n | n >= 1} because it can transition between states for each a and then each b.
    Example improved answer:A finite state machine has strictly finite memory and cannot count an arbitrarily large number of symbols. Therefore, the language L = {a^n b^n | n >= 1} is context-free, not regular, and cannot be recognised by a finite state automaton.
    Examiner Tip: Remember: regular languages cannot handle unbounded nested structures or memory counting. If a language requires counting matching pairs of arbitrary length, it is not regular.
    Step-by-Step Worked Solutions

    Question: Consider the alphabet Sigma = {0, 1}. Write a regular expression that defines the language of all strings that begin with a '1' and end with a '0', with any sequence of 0s and 1s in between. Explain how an equivalent deterministic finite state machine (DFA) would accept this language.

    1. 1.Step 1: Identify the starting and ending constraints. The string must start with '1' and terminate with '0'.
    2. 2.Step 2: Define the intermediate characters. Between the first '1' and the last '0', any combination of '0' and '1' is permitted, including none. This is represented by (0|1)*.
    3. 3.Step 3: Combine these parts to formulate the regular expression: 1(0|1)*0.
    4. 4.Step 4: Design the DFA transitions. Define four states: S0 (start state), S1 (read initial '1' or subsequent '1's), S2 (accepting state, reached upon reading '0' after an initial '1'), and S_trap (dead state, reached if initial input is '0').
    5. 5.Step 5: Ensure from S2, an input of '0' stays in S2, while an input of '1' transitions back to S1, guaranteeing acceptance occurs if and only if the final consumed symbol is '0'.
    Final Answer: The regular expression is 1(0|1)*0. The equivalent DFA requires a start state, an intermediate state representing strings ending in 1, an accepting state representing strings ending in 0, and a trap state for invalid prefixes.

    Question: Show that the language consisting of all strings over {a, b} containing an odd number of 'a's is regular by constructing the transition table for a deterministic finite state machine (DFA).

    1. 1.Step 1: Determine the states needed to track parity. We only need two states: S_even (an even number of 'a's seen so far) and S_odd (an odd number of 'a's seen so far).
    2. 2.Step 2: Assign initial and accepting states. Start in S_even (0 is an even number). The accepting state is S_odd.
    3. 3.Step 3: Define transitions for 'a'. Reading 'a' flips parity: delta(S_even, a) = S_odd, and delta(S_odd, a) = S_even.
    4. 4.Step 4: Define transitions for 'b'. Reading 'b' preserves parity: delta(S_even, b) = S_even, and delta(S_odd, b) = S_odd.
    5. 5.Step 5: Summarise transitions in a formal state transition table.
    Final Answer: Transition Table: State S_even (Start) -> input 'a' goes to S_odd, input 'b' goes to S_even. State S_odd (Accepting) -> input 'a' goes to S_even, input 'b' goes to S_odd.
    Active Recall Memory Test
    What computational model is capable of recognising any regular language?
    Key Fact: A Finite State Machine (or Finite State Automaton), whether deterministic or non-deterministic.
    What does the Kleene star operator (*) represent in a regular expression?
    Key Fact: Zero or more repetitions of the preceding character or group.
    Why can an FSM not recognise the language of balanced parentheses?
    Key Fact: Because an FSM has finite memory and cannot count an arbitrarily deep level of nested brackets.
    Frequently Asked Questions
    What is the difference between a regular language and a context-free language?
    A regular language can be recognised by a finite state machine with fixed, finite memory and defined by regular expressions. A context-free language requires a pushdown automaton (a machine with a stack) because it involves structures requiring matching or nested pairs, such as mathematical expressions and programming language syntax. Regular languages are a strict subset of context-free languages.
    Does an NFA accept more languages than a DFA?
    No. In formal language theory, Non-deterministic Finite Automata (NFAs) and Deterministic Finite Automata (DFAs) have identical expressive power. Any language accepted by an NFA can also be accepted by an equivalent DFA, although the DFA may require up to 2^n states where n is the number of states in the NFA.
    Why is the empty string important in regular languages?
    The empty string, often denoted by epsilon or lambda, represents a string of length zero. It is crucial because operations like the Kleene star (*) explicitly include the empty string as a valid match. Knowing whether a language includes the empty string determines whether the start state of an equivalent finite state machine must also be an accepting state.
    How do regular languages relate to compilers in computer science?
    Regular languages are used during the lexical analysis stage of a compiler. The compiler's lexer uses regular expressions to identify and tokenize source code keywords, identifiers, and literals before passing them to the syntax analyser. The subsequent syntax analysis stage requires context-free grammars because code contains nested blocks and expressions.