Finite automata and pattern matching – the barbara problem

Intro

Ever heard of the name Barbara? It's fairly common in the place where I live. Except the commonness, word Barbara has some special features. It consist only of 3 letters and it the substring bar appears twice. This word is a perfect example on how to use deterministic finite automata (DFA, explained in the article) for pattern matching and substring searching.

Finite automata?

An automaton (in automata theory) is a 5-tuple (Q, Σ, δ, q0, F) defined as following:

  • Q – Finite set of states
  • Σ – Alphabet
  • δ – Transition function (δ: Q × Σ → Q)
  • q0 – First (starting) state
  • F – Set of finishing (accept) states

Before I go further, I have to define that a string is an array of symbols over Σ (labeled as Σ*, where * is a Kleene star, also called an iterator). Basically, an automaton is a machine that takes a string and either accepts it or declines it (go figure). The string is accepted if the automaton is left in a finishing (accept) state after "reading" it. "Reading" the string is done symbol by symbol where each symbol is fed to the transition function that determines what the next state will be. If the automaton is not in an accept state at the end, the string gets declined. Finite automata can be divided into two subgroups. Automata can be either deterministic (DFA) or nondeterministic (NFA), based on the way they "read". From now on, I'll use acronyms for both. DFA, is, as the name states, deterministic, meaning the transition from one state to another is unique. NFA is the opposite, transition doesn't have to be unique, meaning that automaton can go from one state to several different states by "reading" just one symbol. That said, DFA accepts a string if there's a unique path from starting state to one of the accept states, and NFA accepts a string if a path exists, no matter how it's formed. Even though these two seem quite different, both of them accept the same group of languages over Σ, and every NFA can be converted to DFA and vice versa. Languages that finite automata accept are called Regular languages (Kleene theorem) and can be represented by a regular expression. I believe that's quite enough of math theory for now. The last thing I need to say is that finite automata is usually represented by a directed graph where arrows represent the transition function.

The barbara

As I've stated in the intro, barbara is a fun word. It consists of just three letters (b, a, r) and has the substring bar repeated twice. That makes it specially interesting. Why? Because you can't just check only if b precedes a, a precedes r and so on. Given a random string of text, how can we determine if barbara appears in it? Sure, we could use one of the many substring searching algorithms (Knuth–Morris–Pratt, Boyer-Moore and many other), but why not do something a lot more interesting, like constructing a DFA for it? If you read the theory in the paragraph above, you know that a properly constructed DFA will accept a random string iff (if and only if) it is left in an accept state after "reading" the string. Automaton given on the graph below will be left in an accept state iff it contains barbara as a substring. Let's get on with the construction.

In order to detect barbara, we will need 8 states and only one of them will be an accept state (first seven will be for checking what precedes what). So, our set Q will be Q = {0, 1, 2, 3, 4, 5, 6, 7}. For the alphabet Σ, we will use the standard English alphabet. Strings over Σ are all words that can be generated using letters of the English alphabet (labeled as Σ*) (they absolutely don't have to have a meaning, as this article is not connected to linguistics in any way). The transition function δ is represented by the arrows on the graph below. Our starting state will be 0, and accept state set will be F = {7}. Desiging δ is the hardest part of the process, of course.

The transition function displayed on the graph is the following:

	δ(3, b) = 4; 		// bar -> barb
	δ(6, b) = 4; 		// barbar -> barb
	δ({0, s}, b) = 1;   		// x -> b

	δ(1, a) = 2; 		// b -> ba
	δ(4, a) = 5;		// barb -> barba
	δ(6, a) = 7;		// barbar -> barbara (the end)
	δ(s, a) = 0;		// x -> λ (empty word)

	δ(2, r) = 3;		// ba -> bar
	δ(5, r) = 6;		// barba -> barbar
	δ(s, r) = 0;		// x -> λ

	δ(s, x) = 0;		// x -> λ	

    s is a variable state not included in the definition

As you can see, the automaton will be in the finishing state iff it recognizes barbara as a substring. When it gets to the finishing state, the loop will make it stay there. Let's try it out and see how it works. For the example, I'll use the transition function and I'll show you each step. Before that, I have to state that δ(s, abc) = δ(δ(s, a), bc), meaning that the word can be broken at any place and we will still get the same results.

	δ(0, oifsfscnbarbakjkjibarbarabkf) = 

	δ(δ(0, oifsfscn), barbakjkjibarbarabkf) = 

	δ(0, barbakjkjibarbarabkf) = 

	δ(δ(0, bar), bakjkjibarbarabkf) = 

	δ(3, bakjkjibarbarabkf) = 

	δ(δ(3, ba), kjkjibarbarabkf) = 

	δ(5, kjkjibarbarabkf) = 

	δ(δ(5, kjkji), barbarabkf) = 

	δ(0, barbarabkf) = 

	δ(δ(0, barbara), bkf) = 

	δ(7, bkf) = 7 which is an accept state.

The algorithms

The last part of the article, are, of course, the implementations. It wouldn't make a lot of sense to just talk about math and not utilize the talk in some way. This time, I'll implement the algorithm in three different languages, just so you can see the differences between three programming paradigms. The first one is Scheme (functional language, a lisp dialect), the second one is Prolog (a widely known logic language) and the third one is C++ (a purely procedural language) this time. I'm giving Java a lil' break today.

Scheme code

(define findbarbara (lambda (string)
  (letrec
    (
      (barbaraDFA (lambda (state string)
        (if (= state 7)
        	#t
        	(if (null? string)
				#f
        		(barbaraDFA (transit state (car string)) (cdr string))
        	)
       	)
       )
      )       

      (transit (lambda (state input)
			  (cond
			    ((eqv? input 'b)
			      (cond
			        ((= state 3) 4)
			        ((= state 6) 4)
			        (else 1)
			      )
			    )
			    ((eqv? input 'a)
			      (cond
			        ((= state 1) 2)
			        ((= state 4) 5)
			        ((= state 6) 7) ; We're done
			        (else 0)
			      )
			    )
			    ((eqv? input 'r)
			      (cond
			        ((= state 2) 3)
			        ((= state 5) 6)
			        (else 0)
			      )
			    )
			    (else 0)  ; The X arrow
			  )
			 )
       )
    )
    (barbaraDFA 0 string) ; 0 is the starting state
  )
)
)

Prolog code

barbaraDFA([_|_], 7).
barbaraDFA([H|T], X) :- X =\= 7, transit(H, X, X1), barbaraDFA(T, X1).

transit(b, 3, 4).
transit(b, 6, 4).
transit(b, _, 1).
	
transit(a, 1, 2).
transit(a, 4, 5).
transit(a, 6, 7).
transit(a, _, 0).
	
transit(r, 2, 3).
transit(r, 5, 6).
transit(4, _, 0).
	
transit(_, _, 0).
	
findBarbara(X) :- barbaraDFA(X, 0).

C++ code

#include <iostream>

using namespace std;

int main() {
	char str[100];
	int state = 0, i = 0;

	cin >> str;

	while(state != 7 && str[i] != '\0') {
		switch(str[i++]) {
			case 'b':
				if(state == 3 || state == 6) 
					state = 4;
				else 
					state = 1;
			break;
			case 'a':
				if(state == 1)
					state = 2;
				else if(state == 4)
					state = 5;
				else if(state == 6)
					state = 7;
				else 
					state = 0;
			break;
			case 'r':
				if(state == 2)
					state = 3;
				else if(state == 5)
					state = 6;
				else 
					state = 0;
			break;
			default:
				state = 0;
			break;
		}
	}

	if(state == 7)
		cout << "#t";
	else 
		cout << "#f";

	return 0;
}

Outro

Even though this possibly seems as a harder way to achieve substring search than using regular widely-known algorithms, finite automata can also be used to match not only substrings but also regular expressions of all kinds. As I've said, DFA's accept regular languages and a language is regular iff it has a regular expression representing it.


Markov Composer - Using machine learning and a Markov chain to compose music

Edit: If you want to see MarkovComposer in action, but you don't want to mess with Java code, you can access a web version of it here.

Intro

In the following article, I'll present some of the research I've been working on lately. Algorithms, or algorithmic composition, have been used to compose music for centuries. For example, Western punctus contra punctum can be sometimes reduced to algorithmic determinacy. Then, why not use fast-learning computers capable of billions of calculations per second to do what they do best, to follow algorithms? In this article, I'm going to do just that, using machine learning and a second order Markov chain.

A graph representing a Markov chain transition matrix (explained after) with 8 compositions learned.

Markov chain?

Markov chain, named after Andrey Andreyevich Markov (look, we even share the first name), is a (pseudo)random process of transition from one state to another. The transition is "memoryless" and it only depends on the current state and on the probabilities (saved in a so-called transition matrix). Sequence of events that preceeded the current state should in no way determine the transition. This "memorylessness" is also called Markov property. In short, transiting from one state to another is a random process based on probability.

The general idea

Markov chain is just plain perfect for algorithmic music compositions. Notes (128 of them) are used as possible states. For the implementation, I'm using a second order Markov chain, meaning two previous states (two previous notes) determine the next state and nothing else. All of the transition probabilites are stored in a 2^14x2^7 matrix. As input, the composer takes two integer values (0 <= n, m <= 127) representing 2 starting notes. Based on that the algorithm calculates/generates the next note and the generation process goes ad infinitum (until you stop it, that is). For the simplicity, currently, all the notes are played at the same pitch (127) and at the same time spacing between notes (300ms).

Calculating probabilities and weights for Markov chain transition matrix

Generating a Markov chain transition matrix (MCTM in future use) is based on a very simple principle. First of, a weight matrix is used (WM in future use). As I've stated before, since the algorithm is based on a second order Markov chain, the calculation process involves three notes. For every three notes, the first two are the "first" state and the third one is a second state, and therefore the following field WM[first_note*127+second_note][third_note] is just incremented by one. Of course, this is just the beginning of the process. After all of the weights have been incremented accordingly, and the WM is completely generated, it is "normalized"/converted to a MCTM by converting integer values to their percentage relative to the sum of all values in the row, effectively generating a complete MCTM. The code snippets below show both processes respectively. Both matrices are represented by a single one, called scoreMatrix.

WM generation

		public static void updateWeight(int n1, int n2, int n3) {
			scoreMatrix[n1*127+n2][n3]++;
		}
	

WM normalization/MCTM generation

		public static int sumAll(int pos) {
			int sum = 0;

			for(int i = 0; i < 128; sum+=scoreMatrix[pos][i++]);

			return sum;
		}

		public static void normalizeMatrix() {
			for(int i = 0; i < 128*128; i++) {
				int sum = sumAll(i);
				if(sum != 0)
					for(int j = 0; j < 128; j++) 
						scoreMatrix[i][j] /= sum;					
			}
		}
	

The actual learning process

Learning process at the ends returns a generated WM matrix. After all of the learning is completed, the matrix is converted to a MCTM. Algorithm described in this article uses MIDI files (.mid) for learning. It processes the file note by note, updating the WM matrix accordingly, as described in the paragraph above. The iteration through the MIDI file is achieved by using Java's builtin Sequencer.

		public Learn(String midiName) {
			try {
				Sequence sequence = MidiSystem.getSequence(new File(midiName));

				int id[] = {0, 0, 0};
				int nArr[][] = new int[2][2];

				for(Track track : sequence.getTracks()) {
					for(int i = 0; i < track.size(); i++) { 				
						MidiEvent event = track.get(i);
						MidiMessage message = event.getMessage();
						if(message instanceof ShortMessage) {
							ShortMessage sm = (ShortMessage) message;

							if(sm.getCommand() == NOTE_ON) {
								int key = sm.getData1();

								for(int j = 0; j < 2; j++) {
									if(id[j] == 2) {
										id[j] = 0;
										Score.updateWeight(nArr[j][0], nArr[j][1], key);
									} else {
										nArr[j][id[j]++] = key;
									}
								}
							}
						}
					}
				}

				cnt++;
			} catch(InvalidMidiDataException|IOException e) {
				e.printStackTrace();
			}
		}
	

Choosing the right note

Yaay, we are on the most important part yet! All of the code above would be useless if we didn't have a way to generate the right note. The process is actually quite simple, and it's based on randomness, the current state (last two notes in the sequence), and, of course, the MCTM generated before. The chance is randomly generated using Java's builtin Math.random() function. Then, the aglorithm is iterating through the MCTM to find the note with the correct (closest) probability and returns it. (returns a value between 0 and 127)

		public static int nextNote(int n1, int n2) {
			double rnd = Math.random();
			double sum = 0.0;

			for(int i = 0; i < 128; i++) {
				sum += scoreMatrix[n1*127+n2][i];

				if(sum >= rnd)
					return i;
			}

			return (int) (rnd*127);	/* In an off chance that no states are found (all have 0.0 probability of transition), the algorithm continues randomly */
		}
	

Playing the output

The output is played by the Java's builtin Synthesizer, and the notes are generated on the go by the algorithm above, based on the previously generated MCTM. The output is mainly determined by the two starting notes, chosen either randomly or by the user.

		try {				
			Synthesizer synth = MidiSystem.getSynthesizer();
			synth.open();

			final MidiChannel[] channels = synth.getChannels();

			int fn, sn, nn;

			fn = n1;
			sn = n2;

			while (!this.isInterrupted()) {
				nn = Score.nextNote(fn, sn);

				int octave = (nn/12)-1;
				String noteName = NOTE_NAMES[nn%12];

				channels[0].noteOn(nn, Info.NOTE_VELOCITY);
				Thread.sleep(Info.NOTE_PAUSE);
				channels[0].noteOff(nn);

				fn = sn;
				sn = nn;
			}
		} catch(Exception e) {}
	

The final (alpha) product

An image representing the main screen of the application

Samples

Just an example what can Markov composer do. Based on a little bit of testing, there are probably a lot more, a lot better generated compositions.

Outro

Even though this is just an experiment, the results produced are not in total disharmony, and some starting combinations can produce pleasent sounding compositions.

The full code including the GUI is open-source and is publicly available at my github repository.


Conway's Game of Life - Trying it on images

The beginning

In the previous article I wrote about pixel sorting. Today, in this article, I'm going to show you what can Life do to an image. It can also generate glitch art or databending in a totally different way. The transformation below is an example what can happen after 1000 living generations.

In this example, red pixels were used as alive cells.

What is Conway's Game of Life?

Game of Life, or simply, Life is a cellular automation devised by a famous British mathematician John Conway. It's a simple zero-player game and it's result is determined by the initial configuration. The game has four simple rules that cells follow. If the cell is alive and it has less than 2 living neighbours or more than 3 living neighbours, it dies from underpopulation or overpopulation respectively. If it has 2 or 3 living neighbours it survives. If the cell is dead and if it has exactly 3 living neighbours, it becomes alive as if by division. That's basically all the info you need to know for the sake of this article. The only other thing I'll state is that Life is a Turing-complete machine, so with right initial states it can "do" any computer algorithm.

The idea

As I've said the game needs a way to know which cells are alive and which are not, and for this, I'll use pixels. As I've stated in the previous article, each pixel is just an object represented by a 32-bit integer that can be split into four 8-bit integers that determine it's core color values (RGB values). Since every color is represented by an 8-bit integer, the value ranges from 0 to 255. These values will determine our cells. The cell is alive if it's (red/green/blue) color value is over 200.

The algorithm(s)

All of the code snippets below are written in Java and are a part of open-source project PxlSort. The whole code and project can be freely accessed at my github repository.

Loading the image

For keeping images in memory, I’m going to use a standard Java structure called BufferedImage. It’s perfect for sorting because of the following two methods:

		int getRGB(int x, int y); /* returns the 32-bit integer representation of a pixel at x, y */
		void setRGB(int x, int y, int rgb); /* sets 32-bit RGB value to the pixel at x, y */
Determining core color values is quite simple.
		getRGB(x, y) & 0x00ff0000 >> 16; /* returns the first 8-bit value - red color */
		getRGB(x, y) & 0x0000ff00 >> 8; /* returns the second 8-bit value - green color */
		getRGB(x, y) & 0x000000ff;  /* returns the third 8-bit value - blue color */
Now that the image is in memory we can get onto the main algorithm, the Game of Life.

The Game of Life

First, we need a simple wrapper function that determines how much generations we will simulate and which color will determine alive cells.

public void gof(int iter, int by) { 
		this.by = by;
		
		for(int i = 0; i < iter; i++) 
			gameOfLife();
	}

Now for the actual life algorithm. For this, we will need two different methods.

First one is manCell, a method used to kill or create living cells. The idea here is the following: If a cell dies, it gets replaced with a dead neighbour. If a cell is born, it takes the form of another living neighbour. I use these rules so the pixels in the image remain as untouched as possible.

public void manCell(int i, int j, int state) {
		int value;
		
		for(int x = 0; x < 3; x++) {	
			try {
				if(by == 1)
					value = (image.getRGB(i-1, j+x-1) & 0x00ff0000) >> 16;
				else if(by == 2)
					value = (image.getRGB(i-1, j+x-1) & 0x0000ff00) >> 8;
				else 
					value = (image.getRGB(i-1, j+x-1) & 0x000000ff);
				
				if((value > Info.ALIVE_CONSTANT && state == 1) || (value <= Info.ALIVE_CONSTANT && state == 0)) {
					image.setRGB(i, j, image.getRGB(i-1, j+x-1));
					return;
				}
			} catch(ArrayIndexOutOfBoundsException e) {}
		}

		for(int x = 0; x < 3; x++) {
			try {
				if(by == 1)
					value = (image.getRGB(i+1, j+x-1) & 0x00ff0000) >> 16;
				else if(by == 2)
					value = (image.getRGB(i+1, j+x-1) & 0x0000ff00) >> 8;
				else 
					value = (image.getRGB(i+1, j+x-1) & 0x000000ff);

				if((value > Info.ALIVE_CONSTANT && state == 1) || (value <= Info.ALIVE_CONSTANT && state == 0)) {
					image.setRGB(i, j, image.getRGB(i+1, j+x-1));
					return;
				}
			} catch(ArrayIndexOutOfBoundsException e) {}
		}

		for(int x = 0; x < 2; x++) {
			try {
				if(by == 1)
					value = (image.getRGB(i, j+2*x-1) & 0x00ff0000) >> 16;
				else if(by == 2)
					value = (image.getRGB(i, j+2*x-1) & 0x0000ff00) >> 8;
				else 
					value = (image.getRGB(i, j+2*x-1) & 0x000000ff);

				if((value > Info.ALIVE_CONSTANT && state == 1) || (value <= Info.ALIVE_CONSTANT && state == 0)) {
					image.setRGB(i, j, image.getRGB(i, j+2*x-1));
					return;
				}
			} catch(ArrayIndexOutOfBoundsException e) {}
		}
	}
    

Using these try and catch blocks is not really a nice programming style, but it does the job and eliminates unnecessary if clauses.

For the main algorithm, I use the following method. It loops through all the pixels (read cells) and determines what happens to each.

	public void gameOfLife() {
		int h = image.getHeight();
		int w = image.getWidth();

		for(int i = 0; i < w; i++) {
			for(int j = 0; j < h; j++) {				
				int val;

				if(by == 1)
					val = (image.getRGB(i, j) & 0x00ff0000) >> 16;
				else if(by == 2)
					val = (image.getRGB(i, j) & 0x0000ff00) >> 8;
				else 
					val = (image.getRGB(i, j) & 0x000000ff);	

				boolean alive = val > Info.ALIVE_CONSTANT;
		
				int value, aliveNeighbours = 0;
		
		
				for(int x = 0; x < 3; x++) {	
					try {
						if(by == 1)
							value = (image.getRGB(i-1, j+x-1) & 0x00ff0000) >> 16;
						else if(by == 2)
							value = (image.getRGB(i-1, j+x-1) & 0x0000ff00) >> 8;
						else 
							value = (image.getRGB(i-1, j+x-1) & 0x000000ff);
		
						aliveNeighbours = aliveNeighbours + (value > Info.ALIVE_CONSTANT ? 1 : 0);
					} catch(ArrayIndexOutOfBoundsException e) {}
				}
		
				for(int x = 0; x < 3; x++) {
					try {
						if(by == 1)
							value = (image.getRGB(i+1, j+x-1) & 0x00ff0000) >> 16;
						else if(by == 2)
							value = (image.getRGB(i+1, j+x-1) & 0x0000ff00) >> 8;
						else 
							value = (image.getRGB(i+1, j+x-1) & 0x000000ff);
		
						aliveNeighbours = aliveNeighbours + (value > Info.ALIVE_CONSTANT ? 1 : 0);
					} catch(ArrayIndexOutOfBoundsException e) {}
				}
		
				for(int x = 0; x < 2; x++) {
					try {
						if(by == 1)
							value = (image.getRGB(i, j+2*x-1) & 0x00ff0000) >> 16;
						else if(by == 2)
							value = (image.getRGB(i, j+2*x-1) & 0x0000ff00) >> 8;
						else 
							value = (image.getRGB(i, j+2*x-1) & 0x000000ff);
		
						aliveNeighbours = aliveNeighbours + (value > Info.ALIVE_CONSTANT ? 1 : 0);
					} catch(ArrayIndexOutOfBoundsException e) {}
				}
		
				if(alive && (aliveNeighbours < 2 || aliveNeighbours > 3)) 
					manCell(i, j, 0);
				else if(!alive && aliveNeighbours == 3) 
					manCell(i, j, 1);		
			}
		}

	}
    

That's basically it. The effects this simple game produces can truly be magnificent.