A regular language

The module enrollment problem we’ve been discussing requires input from staff, about which combinations of modules students should be able to take, and from students, about which modules each student wants to take. So far we only have a language for the input from staff. In reality the students would probably select modules from some sort of web interface, but for the implementer it would be much easier just to provide a language for their input as well. The simplest such language would have statements which are just lists of modules. The statement “Statistics Algebra”, for example, would have the interpretation “I want to take Statistics and Algebra and nothing else”.

If our language includes all such lists of modules then no parsing is really needed. The lexical analyser, which splits the input into tokens, i.e. module names, does all the work.

There’s another option though. At the point where students are entering their module selections the staff have already entered all the information about allowed combinations. We could define a language consisting of precisely those module lists which are allowed. The information collected from the staff implicitly gives this language a grammar and grammatically correct just means allowed by the module selection rules. Of course any change to those rules gives us a new language.

What sort of language is this? It turns out to be regular. It is possible to create a finite state automaton which recognises it. In fact the example of a finite state automaton I gave you earlier is essentially the one which enforces the rule “Probability ∧ Statistics ∨ Algebra ∧ Geometry”. I just shortened each of the module names to just their initial letter to avoid clutter in the diagram.

One way to construct a module enrollment system would be to use the following components:

I’m not saying you should construct a module enrollment system this way, merely noting that you can.