A2 and the wider world (Part II)

The other connection between A2 and the larger concepts of computer science is found in a different, and perhaps better way of handling the matching of regexes.

If you've looked far enough ahead into computer science you will undoubtedly uncover a field known as automata theory. I won't go into too much detail on this, however we do cover it in later year courses. Essentially it is the study of what are called automata, or abstract machines. Having an understanding of automata and how they work provides a very nice solution to A2.

Regexes themselves are what are known as finite state machines. As they read in the input values, they will take on a certain state, and depending on what the input was and what the transition behaviour of the machine is, it will then proceed to another state.

Within the scope of A2 heres how it works:



We begin in our initial state, and look to the first edge for the initial character.

If that character is an a, we can move on to our accepting state then check the rest. if the next character is a b, we move into an intermediate state, then back to the accepting state if the following character is a c.

If any of these conditions fail we move into the rejecting state, and for our purposes return False.

In pseudocode:

state = initial
if state == initial:
    if s[0] != 'a':
        return false # rejecting state
    elif s[0] == 'a':
        state = final
if state == final:
    if s[i] == 'b':
        state = inter
    if i == len(s) -1:
         return True
if state == inter:
    if s[i] == 'c':
         state = final
    else:
         return False

As I said before, everything eventually ties together. A2 more so than most.