Posts

Showing posts from 2014

Counter-state machines, continued

Image
In a previous post I illustrated a way to count how many strings there are in a formally defined "regular language". One question was, supposing the state machine that recognizes the language has states from which no accepting state is reachable; is its observability matrix still full rank? The answer is no, and here's an example of that, and how to work around it. First, the regular language. Define the alphabet of symbols as "0" and "1", and the grammar rule is this: a finite string is in the language if and only if it contains no "11" substring. Thereafter, I'll use the notions introduced in that previous post. The resulting state machine is given below (initial state omitted), where the "_0" state corresponds to a string ending with "0" and "_1" corresponds to a string ending with "01". "meh" is a rejecting state, meaning the string contains a "11" substring. I'll li

Hangman, entropy, and the robustness of stupid

One of the "procrastination tools" on Critique Circle is a little game of hangman, and I sure sunk a lot of time guessing (and sometimes failing to guess) words there. The rules are fairly simple and you probably know them. You start by knowing how many letters the word has. You guess a letter; if the guess is right, you get to see where the letter appears in the word. If you guess wrong, something is added to the hangman drawing, and if it completes because you make too many wrong guesses, you lose. Instead, if you find all the letters before that happens, you win. Simple fun game, but it got me thinking that it's a neat illustration for the concept of information theoretic entropy. Lets imagine then that we have a list of all possible words, and we know (this is VERY important) that the word we have to guess is chosen from this list AND all words are equally likely. Lets ignore the rules of hangman for a while, and ask a question about how we may be able to selec

Counter-State Machines

Image
I've been doing Project Euler problems for the past couple of months (I'm BLANDCorporatio there too). It's very addicting, and I'm now at 151 solved (still 300+ to go, and they aren't getting any easier :P). Project Euler is great for exercising and learning some math, so if you like that and haven't heard of it, check it out. Today I'll post about an imo neat concept I picked up while solving a few problems there. True, these are some of the easier ones I've tackled, but the concept itself has a cute elegance to it, and a decently wide scope of application, so I thought it makes for a good post. I will not discuss Project Euler problems or solutions however . Where'd the fun be in solving them, if one just copied stuff? So then, here's the type of problem I want to tackle: suppose you have some kind of mathematical object defined by a regular expression . Basically, that means the object is described by (or may be taken to be) some string