3.6 KiB
title, published, template
| title | published | template |
|---|---|---|
| The Syntactic Monoid | false | academic |
This semester was theory time. I enrolled in four theoretical computer science classes. One of them was Automata Theory. A concept I struggled with for quite a while during that class were Syntactic Monoids. After a deeper dive and multiple exercises, I think I wrapped my head around the concept now.
Setting the Context
Automata Theory teaches about the mathematical fundamentals surrounding formal languages, automata and their link to algebra. To understand this article you have to be familiar with finite automata and the idea of a formal language. As a reminder, an automaton looks like this:
And a formal language, here given as regular expression, looks like this:
The Free Monoid
The Syntactic Monoid
Now, what the hell is a syntactic monoid and why do I need it?
Constructing the Minimal Automaton from a Given Language and a Given Monoid
The construction is relatively straight forward if you know what to do.
Firstly, write down everything you know:
- the alphabet,
- the language you want to construct the automaton for,
- the monoid itself
Think about the language as a huge pool of words. Everything word you can construct from the given alphabet and the rules of the language can be in this pool.
Now we want to be Moses and part this pool in such a way that we can not only string letters together, but whole words.
As an example, the language a* over the alphabet A={a} contains all of these words: {ε, a, aa, aaa, aaaa,...} Pick any two of them. You can write them next to each other, concatenate them, and any word you pick from this language will still be in the language. Also the direction does not matter. a'a = aa' (' used here to mark a letter to show its movement in the word)
That means, you can not only concatenate single letters "a" one after the other, but also words "aaa", "aaaaaaa", etc. In a way, all of these words are therefore equivalent to each other. As long as you don't suddenly add a "b", it's impossible to break out of the language.
So obviously, this language is very boring. Let's make it a little bit more interesting.
Take the language ab. If you look closely, now the letter you add to a word makes a difference. Take the word "ab". The word is in the language. now we concatenate the letter "b" to the front of the word, resulting in "bab", which clearly is not in the language anymore.
Now, it's our goal to check how this language can be split up in a way, such that we are grouping letters and words that behave equivalent to each other. Let's take the two words "a" and "aa". Both are is in the language. We can add "a" to it from the beginning and the end, resulting in "aa" and "aaa" and both words are still in the language, after this concatenation. Adding a "b" at the beginning, however, results in words outside out of the language: "ba" and "baa". Still: "a" and "aa" behave the same way, because adding an "a" makes us stay in the language, adding a b from the front makes us leave the language. They are syntactically congruent with each other and hence belong in one equivalence class.
If you think about this a little longer, you'll come to the conclusion, that elongating the word with additional "a" does not change this behavior.
"The Algorithm"
Now for an exam where you are asked to produce a Syntactic Monoid, my Algorithm goes as follows:
- Start with writing down the alphabet.
- Pick the neutral element and check for every letter of the alphabet if it is congruent with any of them. If not, great. You got your first equivalence class.
- If it is congruent with any of the