# Regular Languages

The simplest family of languages – and correspondingly, the simplest kind of computing machine – deal with regular languages. A regular language is very limited: there’s no counting, no deep patterns. They really don’t have much in the way of computational power. But they’re still very useful – the ubiquitous regular expression libraries in most programming languages are just easy ways of using regular languages to decompose simple patterned inputs.

The regular languages can be described in three ways: as regular grammars; as regular expressions; or as a kind of computing machine called a finite state machine or finite state automaton.

# 3-Valued Semantics

Before we can move from three-valued logic to fuzzy logic, we need to take a look at semantics – both how conventional two-valued logic handle semantics, and how three-valued logics extend the basic semantic structure. This isn’t exactly one of the more exciting topics I’ve ever written about – but it is important, and going through it now will set the groundwork for the interesting stuff – the semantics of a true fuzzy logic.

What we’ve looked at so far has been propositional 3-valued logics. Propositional logics aren’t particularly interesting. You can’t do or say much with them. What we really care about is predicate logics. But all we need to do is take the three-valued logics we’ve seen, and allow statements to be predicate(object).

In a conventional first-order predicate logic, we define the semantics in terms of a model or interpretation of the logic. (Technically, a logic and an interpretation aren’t quite the same thing, but for our purposes here, we don’t need to get into the difference.)

An interpretation basically takes a domain consisting of a set of objects or values, and does two things:

1. For each atomic symbol in the logic, it assigns an object from the domain. That value is called the interpretation of the symbol.
2. For each predicate in the logic, it assigns a set, called the extension of the predicate. The extension contains the tuples for which the predicate is true.

For example, we could use logic to talk about Scientopia. The domain would be the set of bloggers, and the set of blogs. Then we could have predicates like “Writes”, which takes two parameters – A, and B – and which is true is A is the author of the blog B.

Then the extension of “Writes” would be a set of pairs: { (MarkCC, Good Math/Bad Math), (Scicurious, Neurotic Physiology), … }.

We can also define the counterextension, which is the set of pairs for whiche the predicate is not true. So the counterextension of “writes” would contain values like { (MarkCC, Neurotic Physiology), …}.

Given a domain of objects, and the extension of each predicate, we know the meaning of statements in the logic. We know what objects we’re reasoning about, and we know the truth or falsehood of every statement. Importantly, we don’t need to know the counterextension of a predicate: if we know the extension, then the counterextension is simple the complement of the extension.

In three-valued Lukasiewicz logic, that’s not true, for reasons that should be obvious: if $I(A)$ is the interpretation of the predicate $A$, then the complement of $I(A)$ is not the same thing as $I(lnot A)$. $L_3$ requires three sets for a predicate: the extension, the counterextension, and the fringe. The fringe of a predicate $P$ is the set of values $x$ for which $P(x)$ is $N$.

To be more precise, an interpretation $I$ for first order $L_3$ consists of:

1. A set of values, $D$, called the domain of the logic. This is the set of objects that the logic can be used to reason about.
2. For each predicate $P$ of arity $n$ (that is, taking $n$ arguments), three sets $ext(P)$, $cext(P)$, and $fringe(P)$, such that:
• the values of the members of all three sets are members of $D^n$.
• the sets are mutually exclusive – that is, there is no value that is in more than one of the sets.
• the sets are exhaustive: $ext(P) cup cext(P) cup fringe(P) = D^n$.
3. For each constant symbol $a$ in the logic, an assignment of $a$ to some member of $D$: $I(a) in D$

With the interpretation, we can look at statements in the logic, and determine their truth or falsehood. But when we go through a proof, we’ll often have statements that don’t operate on specific values – they use variables inside of them. In order to make a statement have a truth value, all of the variables in that statement have to be bound by a quantifier, or assigned to a specific value by a variable assignment. So given a statement, we can frequently only talk about its meaning in terms of variable assignments for it.

So, for example, consider a simple statement: P(x,y,z). In the interpretation I, P(x, y, z) is satisfied if $(I(x), I(y), I(z)) in ext(P)$; it’s dissatisfied if $(I(x), I(y), I(z)) in cext(P)$. Otherwise, $(I(x), I(y), I(z))$ must be in $fringe(P)$, and then the statement is undetermined.

The basic connectives – and, or, not, implies, etc., all have defining rules like the above – they’re obvious and easy to derive given the truth tables for the connectives, so I’m not going to go into detail. But it does get at least a little bit interesting when we get to quantified statements. But to talk about we need to first define a construction called a variant. Given a statement with variable assignment v, which maps all of the variables in the statement to values, an x-variant of $v$ is a variable assignment where for every variable $y$ except $x$, . In other words, it’s an assignment where all of the variables except x have the same value as in $v$.

Now we can finally get to the interpretation of quantified statements. Given a statement $forall x P$, $P$ is satisfied by a variable assignment $v$ if $P$ is satisfied by every x-variant of $v$; it’s dissatisfied if $P$ is dissatisfied by at least one x-variant of $v$. Otherwise, it’s undetermined.

Similarly, an existentially quantified statement $exists x P$ is satisfied by $v$ if $P$ is satisfied by at least one x-variant of $v$; it’s dissatisfied if $P$ is dissatisfied by every x-variant of v. Otherwise, it’s undetermined.

Finally, now, we can get to the most important bit: what it means for a statement to be true or false in $L_3$. A statement $S$ is $T$ (true) if it is satisfied by every variable assignment on $I$; it’s $F$ (false) if it’s dissatisfied by every variable assignment on $I$, and it’s $N$ otherwise.

# Friday Random 10

In case you haven’t noticed, the blog in general has been very slow lately. I’ve been overwhelmed, both by work, and by being the administrator for Scientopia. That’s helped turn blogging into more of a job than a hobby. I’m trying to make some changes in how I’m doing things to try to make things fun again.

It’s been a hell of a long time since I did one of these. In fact, I think this might by the first random 10 I’ve posted on Scientopia!

1. Crooked Still, “You Got the Silver”: Crooked Still is a very nice, mildly progressive bluegrass band. Beautifully performed bluegrass music, with a very distinctive style.
2. Sonic Youth, “Alice et Simon”: this is a really intriguing track. Sonic Youth is a band with a very distinctive sound and style. This track has all of the trademarks of SY – and yet, it’s very different from their typical sound.
3. Mogwai, “Danphe and the Brain”: absolutely typical Mogwai. And that’s a very good thing. Mogwai is one of the very best post-rock bands out there.
4. The Tangent, “Grooving on Mars”: a live track from the Tangent. The Tangent started off as a collaboration between Roine Stolte (from the Flower Kings) and Andy Tillison (from Parallel or 90 degrees). Stolte left, and the Tangent has become very much Tillison’s band. They’re fantastic. There’s a strong Flower Kings influence (for obvious reasons), but also a very visible connection to old Genesis, and a variety of other influences. The main problem with the Tangent is that Tillison has some really annoying vocal ticks. But this is an instrumental track, so it doesn’t even have that to hold against it.
5. Punch Brothers, “Ride the Wild Turkey”: Ok, so remember I said up above that Crooked Still was mildly progressive? Well, where CS tries to gently probe the boundaries of what bluegrass is, Punch Brothers attacks them with a hydraulic sledgehammer. It’s hard to say whether Punch Brothers is a bluegrass band with classical influences, or a classical chamber ensemble with bluegrass influences, or a bunch of post-rock geniuses playing with bluegrass. But whatever they are, they’re one of the very best bands in the world. Brilliant musicianship, brilliant compositions, brilliant arrangements… Just all around a thoroughly and delightfully amazing band.
6. The Books, “Idkt”: this is one of my favorite recent discoveries. The Books are a post-rock group that work with found sounds. All of their tracks are built by playing instruments against a backdrop of found sound. They use everything from the voice tracks of old elementary school documentary filmstrips, to traffic noise, to numbers station broadcasts, to the sounds of doors opening and closing in a hallway. They take those found sounds, and they find the music in them. It’s an amazing thing. They’re really not just fitting these sampled sounds into their music; their fitting their music into the found sounds.

7. Naftule’s Dream, “The Unseen”: progressive klezmer. If you like Klez, this is not to be missed.
8. Build, “Imagining Winter”: Lately, I’ve been buying a lot of music from New Amsterdam records. They’re a not-for-profit label that’s operating out of (I think) Brooklyn, which specialized in what they call post-classical music. It’s basically the same sort of stuff as post-rock, but with a very strong classic influence. Build is a very, very good example of the post-classical style. I strongly recommend visiting New Amsterdam’s site. They’ve got samples and free download tracks of just about everyone on the label – so you can get an idea of what they’ll sound like before you buy them. It’s fantastic, innovative music, being built on a model that allows the musicians to survive in the internet world.
9. King Crimson, “Sleepless”: my favorite example of how catchy, dance music doesn’t need to be insipid bullshit. This is King Crimson, at their progressive best – and it’s bouncy-catchy-fun-engaging music, while also being complex, intricate, and experimental.
10. Sunday Driver, “Snow Song”: This is a band that’s really hard to describe. They connect themselves with the Steampunk movement in fiction, but I find it hard to find that in their music. To me, they sound like mid-80s Kate Bush with influences from Indian music. Not something I feel like listenting to every day, but very interesting, and terrific if I’m in the right mood.