{"id":1357,"date":"2011-03-29T21:51:35","date_gmt":"2011-03-30T01:51:35","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1357"},"modified":"2011-03-29T21:51:35","modified_gmt":"2011-03-30T01:51:35","slug":"regular-languages","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/03\/29\/regular-languages\/","title":{"rendered":"Regular Languages"},"content":{"rendered":"

The simplest family of languages – and correspondingly, the simplest kind of computing machine – deal with regular languages<\/em>. A regular language is very<\/em> 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.<\/p>\n

The regular languages can be described in three ways: as regular grammars<\/em>; as regular expressions; or as a kind of computing machine called a finite state machine<\/em> or finite state automaton.<\/p>\n

<\/p>\n

We’ll start with the machines. For each regular language, you can define a simple finite state machine that will determine whether or not a particular string is in the language. In a finite state machine, the machine has a small piece of state – a single atomic value, called the<\/em> state, and it’s allowed to look at exactly one character of input. It’s not allowed to sneak a peak ahead; it’s not allowed to look at any previous characters to see how it got into its current state.<\/p>\n

Let’s get precise. A FSM can be described by a tuple: (Sigma, S, i, f, t), where:<\/p>\n