Corresponding to the hierarchy of idealised machine types there is a hierarchy of languages, with languages classified by which idealised machines are powerful enough to recognise the language, i.e. identify grammatically correct statements in the language. Languages which can be recognised by a finite state automaton are called “regular”. Languages which can be recognised by a pushdown automaton are called “context free”. Languages which can be recognised by a Turing machine are called “recursively enumerable”.
We know that the prefix and postfix versions of our module enrollment language are context free, because we’ve described an algorithm for recognising them which could be implemented by a pushdown automaton.
I didn’t actually describe those algorithms in that way, instead using a non-negative integer as a state variable, but we can simulate non-negative integers with a stack. Zero is the empty stack. We increment by pushing something onto the stack and decrement by popping something off. What we push or pop is irrelevant. The size of the stack at each stage is what we earlier referred to as the counter.
We may strongly suspect that those languages are not regular, but we haven’t proved that yet. Whether the infix version of our module selection language is context free is a question we’ll return to later.
It’s also possible to characterise these classes of languages purely in terms of their grammar, without reference to any idealised computing machine. This characterisation is useful because it’s usually easier to write down a grammar for a language than to design an idealised machine to recognise it.