<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Peter Aarestad on Medium]]></title>
        <description><![CDATA[Stories by Peter Aarestad on Medium]]></description>
        <link>https://medium.com/@aarestad?source=rss-2bdd02cf5da2------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*0I9V8Sf-kMVKn0vs.jpg</url>
            <title>Stories by Peter Aarestad on Medium</title>
            <link>https://medium.com/@aarestad?source=rss-2bdd02cf5da2------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 13:43:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@aarestad/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Formal Languages, Part 2: Regular Expressions and Regular Languages]]></title>
            <link>https://medium.com/@aarestad/formal-languages-part-2-regular-expressions-and-regular-languages-c44f7553035d?source=rss-2bdd02cf5da2------2</link>
            <guid isPermaLink="false">https://medium.com/p/c44f7553035d</guid>
            <category><![CDATA[regex]]></category>
            <category><![CDATA[formal-languages]]></category>
            <dc:creator><![CDATA[Peter Aarestad]]></dc:creator>
            <pubDate>Wed, 25 Feb 2015 00:00:00 GMT</pubDate>
            <atom:updated>2016-01-26T15:42:25.010Z</atom:updated>
            <content:encoded><![CDATA[<p>Before I start in on this entry, I need to give credit where credit is due and note that my main reference source for these blog posts on formal languages is my grad school textbook,<a href="http://www.amazon.com/Introduction-Formal-Languages-Automata-5th/dp/144961552X"> <em>An Introduction to Formal Languages and Automata, Third Edition</em></a> by Peter Linz (the 5th edition is linked). If you’re out there, Peter, thanks for writing an awesome intro to this nerdy topic, and congratulations on having a great first name.</p><p>So let’s talk about regular expressions. Again, we’re not talking about the <a href="http://perldoc.perl.org/perlre.html">Perl </a>version with lazy matching and look-ahead and look-behind and all that magic; we’re discussing austere, formalized regular expressions. The idea is that a regular expression matches a set of strings, and those strings make up a <strong>regular language</strong>. (This is jumping the gun a bit because we actually define regular languages using <strong>finite automata</strong>, but we’ll come back to that later.) For formality’s sake, we first note that the empty set ∅ and the empty string λ themselves are regular expressions; the former is, of course, a set of zero sentences, while the latter is a set of one sentence, namely the empty string. In addition, any member <em>a</em> in a given alphabet Σ is also a regular expression of a single sentence one symbol long. We then add on concatenation (<em>r1</em>·<em>r2</em>, or more simply, <em>r1r2</em>), alternation (<em>r1</em> + <em>r2</em>, which is expressed in Unix and Perl REs as <em>r1</em> | <em>r2</em>, and means “<em>r1</em> or <em>r2</em>“) and star-closure (<em>r*</em>, i.e. zero or more <em>r</em>s in a row), where the <em>r</em>s are composed of the <em>primitive</em> regular expressions ∅, λ, and all <em>a</em> ∈ Σ. (We almost always ignore the ∅ and λ, however, and just talk about combinations of symbols in the alphabet Σ.) We can also group sub-expressions with parentheses. So this way, we can say things like “a language with an even number of <em>a</em>s followed by an odd number of <em>b</em>s”, which would be expressed as:</p><p><em>r</em> = (<em>aa</em>)*(<em>bb</em>)*<em>b</em></p><p>To break that down, we first see that (<em>aa</em>)* represents any number of <em>aa</em>s: 0, 1, 2, etc., and so gives us an even number of <em>a</em>s. The second part, (<em>bb</em>)*<em>b</em>, indicates that we again have an even number of <em>b</em>s, but then there is one extra <em>b</em> at the end, giving us an odd number. We can give many examples of regular expressions: “all bit strings (i.e. strings of 0s and 1s) which has at least one pair of consecutive 0s”, “all strings on an alphabet such that the length is divisible by 3”, “all bit strings that, when interpreted as a binary number, is greater than or equal to 39”, and so on. So it seems like we can define quite a few complicated languages using just this simple way of expressing patterns! However, remember the example from part 1:</p><pre>/^1?$|^(11+?)\1+$/</pre><p>This isn’t a true regular expression, as we noted — you can’t do things in regular expressions like “lazy matching” or “back-referencing”. All we can say is “this followed by that”, “this or that” and “zero or more thises”. But maybe it’s possible that there <em>is</em> a regular expression that does what the above does, namely match all composite numbers expressed in unary notation. Try if you’d like, but you’ll soon see it’s futile. In another post, I’ll explain the goofily-named <strong>pumping lemma</strong> which is used to prove that a particular grammar does not represent a regular language, and thus cannot be represented by a regular expression. We’ll then use the pumping lemma to prove that we can’t construct a regular expression for this language.</p><p>I think that’s enough for now. Next time, we’ll discuss finite automata and how they’re used to truly define regular languages. As a preview, we’ll see that there are two types: <em>deterministic</em> automata which require that you always know what to do next, and <em>non-deterministic</em> automata which allows “guesses” as to how to proceed. The magic part, as we’ll see, is that they are equivalent! But you’ll have to come back later to see what I’m talking about.</p><p><em>Originally published at </em><a href="http://www.peter-aarestad.com/blog/?p=146"><em>www.peter-aarestad.com</em></a><em> on February 25, 2015.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c44f7553035d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Formal Languages Part 1: Basic Concepts]]></title>
            <link>https://medium.com/@aarestad/formal-languages-part-1-basic-concepts-7c6979a91a7b?source=rss-2bdd02cf5da2------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c6979a91a7b</guid>
            <category><![CDATA[formal-languages]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[regex]]></category>
            <dc:creator><![CDATA[Peter Aarestad]]></dc:creator>
            <pubDate>Sun, 15 Feb 2015 00:00:00 GMT</pubDate>
            <atom:updated>2016-01-26T15:39:55.821Z</atom:updated>
            <content:encoded><![CDATA[<p>Last week, there was a <a href="http://www.catonmat.net/blog/perl-regex-that-matches-prime-numbers/">link</a> posted on Hacker News that described a regular expression that only matches non-prime numbers (expressed as a string of “1”s, i.e. in so-called “unary” notation):</p><pre>/^1?$|^(11+?)\1+$/</pre><p><a href="https://news.ycombinator.com/item?id=3391547">Commenters</a> noted that this is not a <em>real</em> regular expression. But what does that mean? Anyone with experience in Perl regular expressions can see that this clearly will work just fine; the linked article does a good job of breaking down how this goes about matching (or not matching) a given string of 1s. You see, the history of Unix has sort of muddied the term “regular expression” to the point that it means something in practice that is broader than the theory. Originally, the old Unix command line tool grep was designed with classical “regular expressions” in mind. However, as is well-known, classical regular expressions are very limited, and so a separate tool called egrep was written to accept so-called “extended regular expressions”, and eventually egrep‘s notion of an extended RE is what we now call a “regular expression”.</p><p>So what is a “classical” regular expression? To explore that question, we need to look into the field called “formal languages”. Despite the name, the field has little to do with programming languages or spoken languages, although it is used in theoretical studies of these kinds of language. Formal language study is the study of patterns, in a way. It asks: what is the simplest pattern which can describe this (usually infinite) set of strings? So to understand what a regular expression is, we need to set down some definitions first that will allow us to talk about formal languages in general. Once we do that, we can talk about the family of so-called “regular languages” that regular expressions encompass, and go beyond that to define more powerful languages.</p><h3>Basic concepts of formal languages</h3><p>A <strong>language</strong> is just a set of <strong>string</strong>s that are constructed from an <strong>alphabet</strong>. An alphabet is simply a finite set of symbols such as ‘a’, ‘b’, ‘c’, etc. Traditionally, an alphabet is denoted with the symbol Σ. Strings are composed of zero or more symbols from the alphabet — the so-called <strong>empty string</strong> is traditionally denoted by λ.</p><p>Since strings can contain many consecutive copies of a particular symbol, we can use a shorthand to represent repetition:</p><p>an= aaaaaa… (n times)</p><p>For n = 0, we define</p><p>a0= λ</p><p>When starting with an alphabet Σ, it’s useful to talk about the possible strings it can make. Σ* is the set of all strings consisting of zero or more symbols from Σ. So say that our alphabet was very simple: it just consisted of {a}. In this case,</p><p>Σ*= { λ, a, aa, aaa, aaaa, … }</p><p>or, more succintly,</p><p>Σ*= { an: n ≥ 0 }</p><p>Σ*always contains λ; if we want to exclude it, we define</p><p>Σ+ = Σ* – { λ }</p><p>A language, then, is just a subset of Σ* – perhaps in a way we can define succinctly, perhaps not. A string that is a member of a language is called a <strong>sentence</strong>. Remember, these are formal, abstract terms, so don’t get too hung-up on the real meaning of “language” or “sentence” here.</p><p>Finally, we have the concept of “grammars”. Again, this isn’t like a grammar you’re used to, although it’s quite close! Sentences in various languages can only be constructed in certain ways; some (like English) are subject-verb-object, some (like Japanese) are subject-object-verb; even others use different combinations. So a basic grammar rule in English is expressed as:</p><p>[<em>sentence</em>] ⇒ [<em>subject</em>] [<em>verb</em>] [<em>object</em>]</p><p>Subjects and objects can be further defined as agglomerations of nouns and articles and such. In the same way, we define grammars with our languages and alphabets:</p><p>G = (V, T, S, P)</p><p>G is a <strong>grammar</strong> described as a combination of three sets and one element:</p><ul><li>V is defined as a set of <strong>variables</strong>; as few as one. These are usually denoted with capital letters such as S, A, B, etc.</li><li>T is defined as a set of <strong>terminal symbols</strong>. This is almost always the alphabet Σ that we are already familiar with</li><li>S is a single member of V, referred to as the <strong>start variable</strong>; by convention, it’s usually just the letter S. This variable is assumed to be, naturally, the start of any derivation using our grammar.</li><li>P is a set of <strong>productions</strong> similar to our grammar rule above. Productions can contain any number of variables and/or terminal symbols on either side of the arrow, though we specify that the left side contains at least one symbol, while the right side can be empty (i.e. λ).</li></ul><p>A language, thus, can be defined as all the sentences such that there is some chain of productions in P called a <strong>derivation</strong> that produces the sentences — we denote this language as L(G), or the language derived from the grammar G.</p><p>To wrap up, here’s a simple grammar:</p><p>G = ({S}, {a, b}, S, P)</p><p>where P is given by the two productions:</p><p>S ⇒ aSb<br>S ⇒ λ</p><p>We can derive the sentence “aabb” as so:</p><p>S ⇒ aSb ⇒ aaSbb ⇒ aabb</p><p>By applying the first rule 0 or more times, followed by the second rule, it’s pretty easy to see that this grammar defines a fairly simple language:</p><p>L(G) = { anbn: n ≥ 0 }</p><p>So now we can talk about formal languages. Next time, we’ll actually get into regular languages, although along the way we will have to detour and talk about “automata”. Robots? Well, not really. More like a robot that defines a language.</p><p><em>Originally published at </em><a href="http://www.peter-aarestad.com/blog/?p=118"><em>www.peter-aarestad.com</em></a><em> on February 15, 2015.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c6979a91a7b" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>