Finite states, sets and regular expressions

By UK A Level Computer Science · independent study · myAudience

Original conceptual plate generated with OpenAI imagegen; inspected in scratch production. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Finite states, sets and regular expressions

An alphabet is a finite set of symbols, such as Σ={0,1}. A word is a finite sequence of symbols, and a language is a set of words over an alphabet. The empty word ε has length zero; it is an element of some languages, not the same thing as the empty language ∅. Sets have no repeated members and no intrinsic order. The cardinality of a finite set is its number of distinct members; a Cartesian product A×B is the set of ordered pairs with first member in A and second in B. If A={E,O} and B={0,1}, their product has four members, matching the four possible state/symbol combinations in our recogniser.

A deterministic finite-state recogniser has a finite state set, a start state, accepting states and a transition for each state/input combination. The current state summarises relevant history. To recognise binary words with an odd count of 1s, only parity matters: E represents an even count and O an odd count. Reading 0 leaves parity unchanged; reading 1 toggles it. Start in E because zero 1s is even. Accept if the final state is O. The invariant after each prefix is that state matches that prefix's parity; an induction on prefix length proves the recogniser's correctness.

The selected FSM plate shows a start arrow into E, 0-labelled self-loops on both states and 1-labelled arrows in both directions. The accepting O has a double circle. Its worked trace 1011 goes E,O,O,E,O and is accepted because it contains three 1s. The arrows represent transitions on individual symbols, not movement through physical space. The complete transition table is δ(E,0)=E, δ(E,1)=O, δ(O,0)=O, δ(O,1)=E. This textual table provides the same information as the plate and remains usable without the image.

A regular expression describes a regular language. Concatenation means successive parts, | gives alternatives, * repeats zero or more times, + repeats one or more and ? makes a part optional. For odd numbers of 1s with arbitrary intervening 0s, one expression is 0*1(0*10*1)*0*: begin with one 1, add pairs of 1s, and allow 0s between and around them. This produces every positive odd count and no even count. Classical regular expressions and finite-state machines describe the same class of languages. Practical regex engines may offer nonregular features such as backreferences, so the equivalence refers to the formal regular-expression operations in the syllabus.

The language is infinite but countable: words can be enumerated by increasing length and then lexicographic order. By contrast, the state set is finite. An infinite language does not imply infinitely many states. The supplied recogniser uses O(n) time and constant state, while its teaching trace uses O(n) storage. A Mealy machine associates output with transitions; this plate is an accept/reject recogniser without transition output. Mealy design, the complete set-operation inventory and broader regular-expression manipulation remain further assessed practice, so this lesson does not close all four mapped blocks.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def odd_ones(word):
"""DFA for odd count of 1s over {0,1}; invalid alphabet fails."""
state = 'E'
trace = [state]
for symbol in word:
if symbol not in '01':
raise ValueError('binary alphabet required')
if symbol == '1':
state = 'O' if state == 'E' else 'E'
trace.append(state)
return state == 'O', trace
```

Worked example: Recognise 1011, 1001 and the empty word, using both the machine and the proposed regex.

1011 toggles on its first 1, stays on 0 and toggles twice more, ending in O.

1001 has two 1s, ending back in E; it cannot be formed as one 1 plus complete pairs of 1s.

The empty word consumes no transition and ends in E. The regex requires at least its initial 1, so it also rejects the empty word.

Answer: 1011 is accepted; 1001 and ε are rejected.

Check your understanding: 1. Give a shortest accepted word. 2. Distinguish {ε} from ∅ and calculate |{E,O}×{0,1}|. 3. Design a recogniser for counts of 1s divisible by three and justify minimal memory in terms of distinguishable remainders.

Answer: 1. "1". 2. {ε} contains one zero-length word; ∅ contains no words; the product has four members. 3. Use states R0,R1,R2, start and accept R0, loop on 0 and advance cyclically on 1. After a prefix, the state stores count modulo three. The remainders must be distinguished: appending zero, one or two 1s can make one remainder divisible by three while leaving another nondivisible.

Why: A zero-length word is still a word. Accepting states describe the end of the entire input, not an early automatic return when the state first becomes accepting. Finite memory can recognise an infinite regular language because it retains a summary rather than every past symbol.