12. FORMAL LANGUAGES

## 12.1\. WHAT’S THE BIG PICTURE?[](http://csfieldguide.org.nz/FormalLanguages.html#what-s-the-big-picture "Permalink to this headline") If you’ve ever written a text-based program, chances are that at some stage the system has told you there’s an error in your program even before it runs.  These “syntax errors” are annoying messages that programmers become excruciatingly familiar with ... it means that they didn’t follow the rules somehow, even if it’s just a tiny mistake. For example, suppose you intended to write: ~~~ x = (a+b)*(c+d) ~~~ but you accidentally left out one of the brackets: ~~~ x = (a+b)*c+d) ~~~ When you try to compile or run the program, the computer will tell you that there’s an error. If it’s really helpful, it might even suggest where the error is, but it won’t run the program until you fix it. This might seem annoying, but in fact by enforcing precision and attention to detail it helps pinpoint mistakes before they become bugs in the program that go undetected until someone using it complains that it’s not working correctly. Whenever you get errors like this, you’re dealing with a *formal language*. Formal languages specify strict rules such as “all parentheses must be balanced”, “all commands in the program must be keywords selected from a small set”, or “the date must contain three numbers separated by dashes”. Formal languages aren’t just used for programming languages — they’re used anywhere the format of some input is tightly specified, such as typing an email address into a web form. In all these cases, the commands that you have typed (whether in Python, Scratch, Snap!, C, Pascal, Basic, C#, HTML, or XML) are being read by a computer program. (That’s right... Python is a program that reads in Python programs.) In fact, the compiler for a programming language is often written in its own language. Most C compilers are written in C — which begs the question, who wrote the first C compiler (and what if it had bugs)?! Computer Scientists have discovered good ways to write programs that process other programs, and a key ingredient is that you have to specify what is allowed in a program very precisely. That’s where formal languages come in. Many of the concepts we’ll look at in this chapter are used in a variety of other situations: checking input to a web page; analysing user interfaces; searching text, particularly with “wild cards” strings that can match any sequence of characters; creating logic circuits; specifying communication protocols; and designing embedded systems. Once you’re familiar with the idea of formal languages, you’ll possess a powerful tool for cutting complex systems down to size using an easily specified format. [](http://xkcd.com/1144/) ## 12.2\. GETTING STARTED[](http://csfieldguide.org.nz/FormalLanguages.html#getting-started "Permalink to this headline") To give you a taste of what can be done, let’s try searching for words that fit particular patterns. Suppose you’re looking for words that contain the name “tim”. Go to the [Regex Dictionary](http://www.visca.com/regexdict/) and type into the “String:” box: ~~~ tim ~~~ then press the “Search” button to find all words containing “tim”. That’s a pretty simple search (though the results may have surprised you!). But now we introduce the *wildcard* code, which in this case is ”.” — a widely used convention. This matches any character at all. So now you can do a search like ~~~ tim.b ~~~ and you will get any words that have both “tim” and “b” with a single character — any character — in between. Are there any words that match “tim..b”? “tim...b”? You can specify any number of occurrences of a symbol by putting a “*” after it (again a widely used convention), so: ~~~ tim.*b ~~~ will match any words where “tim” is followed by “b”, separated by any number of characters — including zero. Try the following search. What kind of words does it find? ~~~ x.*y.*z ~~~ * Can you find words that contain your name, or your initials? * What about words containing the letters from your name in the correct order? * Are there any words that contain all the vowels in order (a, e, i, o, u)? The code you’ve used above is a part of a formal language called a “regular expression”. Computer programs that accept typed input use regular expressions for checking items like dates, credit card numbers and product codes. They’re used extensively by programming language compilers and interpreters to make sense of the text that a programmer types in. We’ll look at them in more detail in the section on [*Regular expressions*](http://csfieldguide.org.nz/FormalLanguages.html#fl-regex). Next we examine a simple system for reading input called a [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton), which — as we’ll find out later — is closely related to regular expressions. Later we’ll explore the idea of *grammars*, another kind of formal language that can deal with more complicated forms of input. ## 12.3\. FINITE STATE AUTOMATA[](http://csfieldguide.org.nz/FormalLanguages.html#finite-state-automata "Permalink to this headline") Here’s a map of a commuter train system for the town of Trainsylvania. The trouble is, it doesn’t show where the the trains go — all you know is that there are two trains from each station, the A-train and the B-train. The inhabitants of Trainsylvania don’t seem to mind this — it’s quite fun choosing trains at each station, and after a while you usually find yourself arriving where you intended.  You can travel around Trainsylvania yourself using the following interactive. You’re starting at the City Mall station, and you need to find your way to Suburbopolis. At each station you can choose either the A-train or the B-train — press the button to find out where it will take you. But, like the residents of Trainsylvania, you’ll probably want to start drawing a map of the railway, because later you might be asked to find your way somewhere else. If you want a template to draw on, you can[print one out from here](http://csfieldguide.org.nz/_static/formal_languages/FL-trainsylvania-blank.pdf). Did you find a sequence of trains to get from City Mall to Suburbopolis? You can test it by typing the sequence of trains in the following interactive. For example, if you took the A-train, then the B-train, then an A-train, type in ABA. Can you find a sequence that takes you from City Mall to Suburbopolis? Can you find another sequence, perhaps a longer one? Suppose you wanted to take a really long route ... can you find a sequence of 12 hops that would get you there? 20 hops? Here’s another map. It’s for a different city, and the stations only have numbers, not names (but you can name them if you want).  Suppose you’re starting at station 1, and need to get to station 3 (it has a double circle to show that’s where you’re headed.) * What’s the shortest way to get from station 1 to station 3? * Where do you end up if you start at station 1 and take the trains ABAA? * Where do you end up if your start at station 1 and take 20 train hops, always alternating A, B, A, B, A, B? * Can you give an easy-to-describe sequence of 100 or more hops that will get you to station 3? The map that we use here, with circles and arrows, is actually a powerful idea from computer science called a [*Finite State Automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton), or FSA for short. Being comfortable with such structures is a useful skill for computer scientists. **Jargon Buster** The name [*Finite State Automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) (FSA) might seem strange, but each word is quite simple. “Finite” just means that there is a limited number of states (such as train stations) in the map. The “state” is just as another name for the train stations we were using. “Automaton” is an old word meaning a machine that acts on its own, following simple rules (such as the cuckoo in a cuckoo clock). Sometimes an FSA is called a **Finite State Machine** (FSM), or even just a “state machine”. By the way, the plural of “Automaton” can be either “Automata” or “Automatons”. People working with formal languages usually use Finite State *Automata*, but “FSAs” for short. An FSA isn’t all that useful for train maps, but the notation is used for many other purposes, from checking input to computer programs to controlling the behaviour of an interface. You may have come across it when you dial a telephone number and get a message saying “Press 1 for this … Press 2 for that … Press 3 to talk to a human operator.” Your key presses are inputs to a [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) at the other end of the phone line. The dialogue can be quite simple, or very complex. Sometimes you are taken round in circles because there is a peculiar loop in the finite-state automaton. If this occurs, it is an error in the design of the system — and it can be extremely frustrating for the caller! Another example is the remote control for an air conditioning unit. It might have half a dozen main buttons, and pressing them changes the mode of operation (e.g. heating, cooling, automatic). To get to the mode you want you have to press just the right sequence, and if you press one too many buttons, it’s like getting to the train station you wanted but accidentally hopping on one more train. It might be a long journey back, and you may end up exploring all sorts of modes to get there! If there’s a manual for the controller, it may well contain a diagram that looks like a [*Finite State Automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton). If there isn’t a manual, you may find yourself wanting to draw a map, just as for the trains above, so that you can understand it better. The map that we used above uses a standard notation. Here’s a smaller one:  Notice that this map has routes that go straight back to where they started! For example, if you start at 1 and take route “b”, you immediately end up back at 1\. This might seem pointless, but it can be quite useful. Each of the “train stations” is called a state, which is a general term that just represents where you are after some sequence of inputs or decisions. What it actually means depends on what the FSA is being used for. States could represent a mode of operation (like fast, medium, or slow when selecting a washing machine spin cycle), or the state of a lock or alarm (on, off, exit mode), or many other things. We’ll see more examples soon. One of the states has a double circle. By convention, this marks a “final” or “accepting” state, and if we end up there we’ve achieved some goal. There’s also a “start” state — that’s the one with an arrow coming from nowhere. Usually the idea is to find a sequence of inputs that gets you from the start state to a final state. In the example above, the shortest input to get to state 2 is “a”, but you can also get there with “aa”, or “aba”, or “baaaaa”. People say that these inputs are “accepted” because they get you from the start state to the final state — it doesn’t have to be the shortest route. What state would you end up in if the input was the letter “a” repeated 100 times? Of course, not all inputs get you to state 2\. For example, “aab” or even just “b” aren’t accepted by this simple system. Can you characterise which inputs are accepted? Here’s an interactive which follows the rules of the FSA above. You can use it to test different inputs. Here’s another [*FSA*](http://csfieldguide.org.nz/appendices/Glossary.html#term-fsa), which looks similar to the last one but behaves quite differently. You can test it in the interactive below.  Work out which of the following inputs it accepts. Remember to start in state 1 each time! * “aaa” * “abb” * “aaaa” * “bababab” * “babababa” * the letter “a” repeated 100 times * the letter “a” repeated 1001 times * the letter “b” a million times, then an “a”, then another million of the letter “b” Can you state a general rule for the input to be accepted? To keep things precise, we’ll define two further technical terms. One is the [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet), which is just a list of all possible inputs that might happen. In the last couple of examples the [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet) has consisted of the two letters “a” and “b”, but for an FSA that is processing text typed into a computer, the [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet) will have to include every letter on the keyboard. The connections between states are called *transitions*, since they are about changing state. The sequence of characters that we input into the FSA is often called a[*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) (it’s just a [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) of letters), and the set of all [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that can be accepted by a particular FSA is called its *language*. For the FSA in the last example, its language includes the [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) “a”, “aaa”, “bab”, “ababab”, and lots more, because these are accepted by it. However, it does not include the [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) “bb” or “aa”. The language of many FSAs is big. In fact, the ones we’ve just looked at are infinite. You could go on all day listing patterns that they accept. There is no limit to the length of the [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) they can accept. That’s good, because many real-life FSA’s have to deal with “infinite” input. The diagram below shows the FSA for the spin speed on a washing machine, where each press of the spin button changes the setting.  It would be frustrating if you could only change the spin setting 50 times, and then it stopped accepting input ever again. If you want, you could switch from fast to slow spin by pressing the spin button 3002 times. Or 2 times would do. Or 2 million times (try it if you don’t believe me). The following diagram summarizes the terminology we have introduced. Notice that this FSA has two accepting states. You can have as many as you want, but only one start state.  For this FSA, the [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) “aa” and “aabba” would be accepted, and “aaa” and “ar” wouldn’t. By the way, notice that we often put inverted commas around [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) to make it clear where they start and stop. Of course, the inverted commas aren’t part of the strings. Sometimes you’ll see an FSA referred to as a Finite State Machine, or FSM, and there are other closely related systems with similar names. We’ll mention some later in the chapter. Now there’s something we have to get out of the way before going further. If we’re talking about which [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) of inputs will get you into a particular state, and the system starts in that state, then the *empty string* — that is, a string without any letters at all — is one of the solutions! For example, here’s a simple [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) with just one input (button a) that represents a strange kind of light switch. The reset button isn’t part of the FSA; it’s just a way of letting you return to the starting state. See if you can figure out which patterns of input will turn the light on: Have you worked out which sequences of button presses turn on the light? Now think about the *shortest* sequence from a reset that can turn it on. Since it’s already on when it has been reset, the shortest sequence is *zero* button presses. It’s hard to write that down (although you could use “”), so we have a symbol especially for it, which is the Greek letter epsilon: ϵ. You’ll come across ϵ quite often with formal languages. It can be a bit confusing. For example, the language (that is, the list of all accepted inputs) of the FSA above includes “aaa”, “aaaaaa”, and ϵ. If you try telling someone that “nothing” will make the light come on that could be confusing — it might mean that you could never turn the light on — so it’s handy being able to say that the*empty string* (or ϵ) will turn the light on. There are different kinds of “nothing”, and we need to be precise about which one we mean! Here’s the FSA for the strange light switch. You can tell that ϵ is part of the language because the start state is also a final state (in fact, it’s the only final state). Actually, the switch isn’t all that strange — data projectors often require two presses of the power button, to avoid accidentally turning them off.  An important part of the culture of computer science is always to consider extreme cases. One kind of extreme case is where there is no input at all: what if a program is given an empty file, or your database has zero entries in it? It’s always important to make sure that these situations have been thought through. So it’s not surprising that we have a symbol for the empty string. Just for variety, you’ll occasionally find some people using the Greek letter lambda (λ) instead of ϵ to represent the empty string. And by the way, the language of the three-state FSA above is infinitely large because it is the set of all [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that contain the letter “a” in multiples of 3, which is {ϵ, aaa, aaaaaa, aaaaaaaaa, ...}. That’s pretty impressive for such a small machine. While we’re looking at extremes, here’s another FSA to consider. It uses “a” and “b” as its [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet).  Will it accept the [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) “aaa”? Or “aba”? Or anything of 3 characters or more? As soon as you get the third character you end up in state 4, which is called a *trap state* because you can’t get out. If this was the map for the commuter train system we had at the start of this section it would cause problems, because eventually everyone would end up in the trap state, and you’d have serious overcrowding. But it can be useful in other situations — especially if there’s an error in the input, so no matter what else comes up, you don’t want to go ahead. For the example above, the language of the FSA is any mixture of “a”s and “b”s, but only two characters at most. Don’t forget that the empty [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) is also accepted. It’s a very small language; the only [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) in it are: {ϵ, a, b, aa, ab, ba, bb}. Here’s another FSA to consider:  It’s fairly clear what it will accept: [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) like “ab”, “abab”, “abababababab”, and, of course ϵ. But there are some missing transitions: if you are in state 1 and get a “b” there’s nowhere to go. If an input cannot be accepted, it will be rejected, as in this case. We could have put in a trap state to make this clear:  But things can get out of hand. What if there are more letters in the [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet)? We’d need something like this:  So, instead, we just say that any unspecified transition causes the input to be rejected (that is, it behaves as though it goes into a trap state). In other words, it’s fine to use the simple version above, with just two transitions. Now that we’ve got the terminology sorted out, let’s explore some applications of this simple but powerful “machine” called the [*Finite State Automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton). ### 12.3.1\. WHO USES FINITE STATE AUTOMATA?[](http://csfieldguide.org.nz/FormalLanguages.html#who-uses-finite-state-automata "Permalink to this headline") Finite state automata are used a lot in the design of digital circuits (like the electronics in a hard drive) and embedded systems (such as burglar alarms or microwave ovens). Anything that has a few buttons on it and gets into different states when you press those buttons (such as alarm on/off, high/med/low power) is effectively a kind of FSA. With such gadgets, FSAs can be used by designers to plan what will happen for every input in every situation, but they can also be used to analyse the interface of a device. If the FSA that describes a device is really complicated, it’s a warning that the interface is likely to be hard to understand. For example, here’s an FSA for a microwave oven. It reveals that, for example, you can’t get from power2 to power1 without going through timer1\. Restrictions like this will be very frustrating for a user. For example, if they try to set power1 it won’t work until they’ve set timer1 first. Once you know this sequence it’s easy, but the designer should think about whether it’s necessary to force the user into that sort of sequence. These sorts of issues become clear when you look at the FSA. But we’re straying into the area of Human-Computer Interaction! This isn’t surprising because most areas of computer science end up relating to each other — but let’s get back to other applications of FSAs.  As we shall see in the next section, one of the most valuable uses of the FSA in computer science is for checking input to computers, whether it’s a value typed into a dialogue box, a program given to a compiler, or some search text to be found in a large document. There are also data compression methods that use FSAs to capture patterns in the data being compressed, and variants of FSA are used to simulate large computer systems to see how best to configure it before spending money on actually building it. **Curiosity** What’s the biggest FSA in the world, one that lots of people use every day? It’s the World-Wide Web. Each web page is like a state, and the links on that page are the transitions between them. Back in the year 2000 the web had a billion pages. In 2008 Google Inc. declared they had found a trillion different web page addresses. That’s a lot. A book with a billion pages would be 50 km thick. With a trillion pages, its thickness would exceed the circumference of the earth. But the web is just a finite-state automaton. And in order to produce an index for you to use, search engine companies like Google have to examine all the pages to see what words they contain. They explore the web by following all the links, just as you did in the train travelling exercise. Only, because it’s called the “web,” exploring is called “crawling” — like spiders do. ### 12.3.2\. ACTIVITY: PRACTICE CREATING FSAS[](http://csfieldguide.org.nz/FormalLanguages.html#activity-practice-creating-fsas "Permalink to this headline") This activity involves constructing and testing your own FSA, using free software that you can download yourself. Before doing that, we’ll look at some general ways to create an FSA from a description. If you want to try out the examples here on a live FSA, read the next two sections about using Exorciser and JFLAP respectively, which allow you to enter FSAs and test them. A good starting point is to think of the shortest string that is needed for a particular description. For example, suppose you need an FSA that accepts all strings that contain an even number of the letter “b”. The shortest such string is ϵ, which means that the starting state must also be a final state, so you can start by drawing this:  If instead you had to design an FSA where the shortest accepted string is “aba”, you would need a sequence of 4 states like this:  Then you need to think what happens next. For example, if we are accepting strings with an even number of “b”s, a single “b” would have to take you from the start state to a non-accepting state:  But another “b” would make an even number, so that’s acceptable. And for any more input the result would be the same even if all the text to that point hadn’t happened, so you can return to the start state:  Usually you can find a “meaning” for a state. In this example, being in state 1 means that so far you’ve seen an even number of “b”s, and state 2 means that the number so far has been odd. Now we need to think about missing transitions from each state. So far there’s nothing for an “a” out of state 1\. Thinking about state 1, an “a” doesn’t affect the number of “b”s seen, and so we should remain in state 1:  The same applies to state 2:  Now every state has a transition for every input symbol, so the FSA is finished. You should now try some examples to check that an even number of “b”s always brings it to state 1. Get some practice doing this yourself! Here are instructions for two different programs that allow you to enter and test FSAs. #### 12.3.2.1\. EXORCISER[](http://csfieldguide.org.nz/FormalLanguages.html#exorciser "Permalink to this headline") This section shows how to use some educational software called “Exorciser”. (The next section introduces an alternative called JFLAP which is a bit harder to use.) Exorciser has facilities for doing advanced exercises in formal languages; but we use just the simplest ones. Exorciser can be downloaded [here](http://www.swisseduc.ch/compscience/exorciser/index.html). When you run it, select “Constructing Finite Automata” (the first menu item); click the “Beginners” link when you want a new exercise. The challenge in each FSA exercise is the part after the | in the braces (i.e., curly brackets). For example, in the diagram below you are being asked to draw an FSA that accepts an input [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) w if “w has length at least 3”. You should draw and test your answer, although initially you may find it helpful to just click on “Solve exercise” to get a solution, and then follow strings around the solution to see how it works. That’s what we did to make the diagram below.  To draw an FSA in the Exorciser system, right-click anywhere on the empty space and you’ll get a menu of options for adding and deleting states, choosing the[*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet), and so on. To make a transition, drag from the outside circle of one state to another (or out and back to the state for a loop). You can right-click on states and transitions to change them. The notation “a|b” means that a transition will be taken on “a” or “b” (it’s equivalent to two parallel transitions). If your FSA doesn’t solve their challenge, you’ll get a hint in the form of a [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) that your FSA deals with incorrectly, so you can gradually fix it until it works. If you’re stuck, click “Solve exercise”. You can also track input as you type it: right-click to choose that option. See the [SwissEduc website](http://www.swisseduc.ch/compscience/) for more instructions.  The section after next gives some examples to try. If you’re doing this for a report, keep copies of the automata and tests that you do. Right-click on the image for a “Save As” option, or else take screenshots of the images. #### 12.3.2.2\. JFLAP[](http://csfieldguide.org.nz/FormalLanguages.html#jflap "Permalink to this headline") Another widely used system for experimenting with FSAs is a program called JFLAP (download it from [http://jflap.org](http://jflap.org/)). You can use it as an alternative for Exorciser if necesary. You’ll need to follow instructions carefully as it has many more features than you’ll need, and it can be hard to get back to where you started. Here’s how to build an FSA using JFLAP. As an example, we’ll use the following FSA:  To build this, run JFLAP and: * click on the “Finite Automaton” button in the control panel. * In the Editor window, click on the picture of a state (with a little q in it), and then click in the window to create states. * To move the states around, click on the arrow tool in the toolbar (leftmost icon). It doesn’t matter where the states are, but you want them to be easy to view. * To put a transition between two states, click on the transition tool (third icon), drag a line between two states, type the label for the transition (“a” or “b” for this exercise), and press return. (The system will offer the empty string (λ) as a label, but please don’t go there!) * To make a transition loop back to a state, just click on the state with the transition tool. * You can choose the start state by selecting the arrow tool (leftmost icon), right-clicking on the state, and selecting “Initial”. Only one state can be the start state, but you can set more than one “Final” (accepting) state in the same way, by right-clicking on them. If you need to change something, you can delete things with the delete tool (the skull icon). Alternatively, select the arrow tool and double-click on a transition label to edit it, or right-click on a state. You can drag states around using the arrow tool. To watch your FSA process some input, use the “Input” menu (at the top), choose “Step with closure”, type in a short string such as “abaa”, and click “OK”. Then at the bottom of the window you can trace the [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) one character at a time by pressing “Step”, which highlights the current state as it steps through the string. If you step right through the [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) and end up in a final (accepting) state, the panel will come up green. To return to the Editor window, go to the “File” menu and select “Dismiss Tab”.  You can run multiple tests in one go. From the “Input” menu choose “Multiple Run”, and type your tests into the table, or load them from a text file.  You can even do tests with the empty [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) by leaving a blank line in the table, which you can do by pressing the “Enter Lambda” button. There are some FSA examples in the next section. If you’re doing this for a report, keep copies of the automata and tests that you do (JFLAP’s “File” menu has a “Save Image As...” option for taking snapshots of your work; alternatively you can save an FSA that you’ve created in a file to open later). #### 12.3.2.3\. EXAMPLES TO TRY[](http://csfieldguide.org.nz/FormalLanguages.html#examples-to-try "Permalink to this headline") Using Exorciser or JFLAP, construct an FSA that takes inputs made of the letters “a” and “b”, and accepts the input if it meets one of the following requirements. You should build a separate FSA for each of these challenges. * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that start with the letter “a” (e.g. “aa”, “abaaa”, and “abbbb”). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that end with the letter “a” (e.g. “aa”, “abaaa”, and “bbbba”). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that have an even number of the letter “a” (e.g. “aa”, “abaaa”, “bbbb”; and don’t forget the empty string ϵ). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that have an odd number of the letter “a” (e.g. “a”, “baaa”, “bbbab”, but not ϵ). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) where the number of “a”s in the input is a multiple of three (e.g. “aabaaaa”, “bababab”). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) where every time an a appears in the input, it is followed by a b (e.g. “abb”, “bbababbbabab”, “bbb”). * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that end with “ab” * [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that start with “ab” and end with “ba”, and only have “b” in the middle (e.g. “abba”, “abbbbba”) For the FSA(s) that you construct, check that they accept valid input, but also make sure they reject invalid input. Here are some more sequences of characters that you can construct FSAs to detect. The input [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet) is more than just “a” and “b”, but you don’t need to put in a transition for every possible character in every state, because an FSA can automatically reject an input if it uses a character that you haven’t given a transition for. Try doing two or three of these: * the names for international standard paper sizes (A1 to A10, B1 to B10, and so on) * a valid three-letter month name (Jan, Feb, Mar, etc.) * a valid month number (1, 2, ... 12) * a valid weekday name (Monday, Tuesday, ...) A classic example of an FSA is an old-school vending machine that only takes a few kinds of coins. Suppose you have a machine that only takes 5 and 10 cent pieces, and you need to insert 30 cents to get it to work. The [*alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet) of the machine is the 5 and 10 cent coin, which we call F and T for short. For example, TTT would be putting in 3 ten cent coins, which would be accepted. TFFT would also be accepted, but TFFF wouldn’t. Can you design an FSA that accepts the input when 30 cents or more is put into the machine? You can make up your own version for different denominations of coins and required total. If you’ve worked with binary numbers, see if you can figure out what this FSA does. Try each binary number as input: 0, 1, 10, 11, 100, 101, 110, etc.  Can you work out what it means if the FSA finishes in state q1? State q2? ### 12.3.3\. ACTIVITY: FIND FINITE STATE AUTOMATA IN EVERYDAY USE[](http://csfieldguide.org.nz/FormalLanguages.html#activity-find-finite-state-automata-in-everyday-use "Permalink to this headline") There are lots of systems around that use FSAs. You could choose a system, explain how it can be represented with an FSA, and show examples of sequences of input that it deals with. Examples are: * Board games. Simple board games are often just an FSA, where the next move is determined by some input (e.g. a number given by rolling dice), and the final state means that you have completed the game — so the first person to the final state wins. Most games are too complex to draw a full FSA for, but a simple game like snakes and ladders could be used as an example. What are some sequences of dice throws that will get you to the end of the game? What are some sequences that don’t?! * Simple devices with a few buttons often have states that you can identify. For example, a remote control for a car alarm might have two buttons, and what happens to the car depends on the order in which you press them and the current state of the car (whether it is alarmed or not). For devices that automatically turn on or off after a period of time, you may have to include an input such as “waited for 30 seconds”. Other devices to consider are digital watches (with states like “showing time”, “showing date”, “showing stopwatch”, “stopwatch is running”), the power and eject buttons on a CD player, channel selection on a TV remote (just the numbers), setting a clock, storing presets on a car radio, and burglar alarm control panels. ### 12.3.4\. ACTIVITY: KARA, THE LADYBUG[](http://csfieldguide.org.nz/FormalLanguages.html#activity-kara-the-ladybug "Permalink to this headline") [SwissEduc](http://www.swisseduc.ch/compscience/) has a programming environment called [Kara](http://www.swisseduc.ch/compscience/karatojava/kara/) (requires Java to be installed), which is a programmable ladybug that (in its simplest version) walks around an imaginary world controlled by actions output by a [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton). The ladybug has (simulated) detectors that sense its immediate surroundings; these serve as input to the FSA. ## 12.4\. REGULAR EXPRESSIONS[](http://csfieldguide.org.nz/FormalLanguages.html#regular-expressions "Permalink to this headline") Note For teachers Regular expressions (regex for short) are closely related to FSAs, as we shall see. Much of the terminology that is needed was already covered in the previous section: we’ll be using languages, [*alphabets*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabets), strings, ϵ / λ, and eventually finite state automata. So the previous section on FSAs needs to be covered before embarking on regular expressions. It may be that students have used regular expressions already, because they are built into many programming languages and are often used when writing script programs. We’ll be looking briefly at such applications — and they’re very relevant — but in formal languages we’re also interested in the limits of what can be represented, and how to convert a regex to an FSA. So there should be something here to get students thinking, even if they’re expert at programming with regexes. We’ve already had a taste of regular expressions in the [*Getting started*](http://csfieldguide.org.nz/FormalLanguages.html#fl-gettingstarted) section. They are just a simple way to search for things in the input, or to specify what kind of input will be accepted as legitimate. For example, many web scripting programs use them to check input for patterns like dates, email addresses and URLs. They’ve become so popular that they’re now built into most programming languages. You might already have a suspicion that regular expressions are related to finite state automata. And you’d be right, because it turns out that every [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) has a [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) that can check for matches, and every [*finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) can be converted to a [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) that shows exactly what it does (and doesn’t) match. Regular expressions are usually easier for humans to read. For machines, a computer program can convert any regular expression to an FSA, and then the computer can follow very simple rules to check the input. The simplest kind of matching is just entering some text to match. Open a new window to the “Rubular” system (a screenshot is shown below) by clicking on the following challenge: [Open Rubular using this link and type the text "cat" into the box labeled "Your regular expression"](http://rubular.com/r/vCD1OSfjAc)  If you’ve only typed the 3 characters “cat”, then it should find 6 matches. Now try typing a dot (full stop or period) as the fourth character: “cat.”. In a regular expression, ”.” can match any single character. Try adding more dots before and after “cat”. How about “cat.s” or “cat..n”? What do you get if you search for ” ... ” (three dots with a space before and after)? Now try searching for “ic.”. The ”.” matches any letter, but if you really wanted a full stop, you need to write it like this “ic\.” — use this search to find “ic” at the end of a sentence. Another special symbol is “\d”, which matches any digit. Try matching 2, 3 or 4 digits in a row (for example, two digits in a row is “\d\d”). To choose from a small set of characters, try “[ua]ff”. Either of the characters in the square brackets will match. Try writing a [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) that will match “fat”, “sat” and “mat”, but not “cat”. A shortcut for “[mnopqrs]” is “[m-s]”; try “[m-s]at” and “[4-6]”. Another useful shortcut is being able to match repeated letters. There are four common rules: * a* matches 0 or more repetitions of a * a+ matches 1 or more repetitions of a * a? matches 0 or 1 occurrences of a (that is, a is optional) * a{5} matches “aaaaa” (that is, a repeated 5 times) Try experimenting with these. Here are some examples to try: ~~~ f+ pf*t af* f*t f{5} .{5}n ~~~ If you want to choose between options, the vertical bar is useful. Try the following, and work out what they match. You can type extra text into the test [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) area if you want to experiment: ~~~ was|that|hat was|t?hat th(at|e) cat [Tt]h(at|e) [fc]at (ff)+ f(ff)+ ~~~ Notice the use of brackets to group parts of the regular expression. It’s useful if you want the “+” or “*” to apply to more than one character. **Jargon Buster** The name [*Regular Expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) is sometimes abbreviated to “regex”, “regexp”, or “RE”. It’s “regular” because it can be used to define sets of strings from a very simple class of languages called “regular languages”, and it’s an “expression” because it is a combination of symbols that follow some rules. [Click here for another challenge: you should try to write a short regular expression to match the first two words, but not the last three](http://rubular.com/r/AdmyZ5aPtD). Of course, regular expressions are mainly used for more serious purposes. Click on the following challenge to get some new text to search: [Open this challenge in Rubular and try the following expressions](http://rubular.com/r/kun5ZaJqlL). The following [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) will find comon NZ number plates in the sample text, but can you find a shorter version using the {n} notation? ~~~ [A-Z][A-Z][A-Z]\d\d\d ~~~ How about an expression to find the dates in the text? Here’s one option, but it’s not perfect: ~~~ \d [A-Z][a-z][a-z] \d\d\d\d ~~~ Can you improve on it? What about phone numbers? You’ll need to think about what variations of phone numbers are common! How about finding email addresses? [](http://xkcd.com/208/) Regular expressions are useful! The particular form of [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) that we’ve been using is for the Ruby programming language (a popular language for web site development), although it’s very similar to regular expressions used in other languages including Java, JavaScript, PHP, Python, and Microsoft’s .NET Framework. Even some spreadsheets have [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) matching facilities. But regular expressions have their limits — for example, you won’t be able to create one that can match palindromes (words and phrases that are the same backwards as forwards, such as “kayak”, “rotator” and “hannah”), and you can’t use one to detect [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that consist of *n* repeats of the letter “a” followed by *n* repeats of the letter “b”. We’ll look at other systems for doing that in the section on *grammars*. But nevertheless, regular expressions are very useful for a lot of common [*pattern matching*](http://csfieldguide.org.nz/appendices/Glossary.html#term-pattern-matching) requirements. ### 12.4.1\. REGULAR EXPRESSIONS AND FSAS[](http://csfieldguide.org.nz/FormalLanguages.html#regular-expressions-and-fsas "Permalink to this headline") There’s a direct relationship between regular expressions and FSAs. For example, consider the following regex, which matches [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that begin with an even number of the letter “a” and end with an even number of the letter “b”: ~~~ (aa)+(bb)+ ~~~ Now look at how the following FSA works on these [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) — you could try “aabb”, “aaaabb”, “aaaaaabbbb”, and also see what happens for [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) like “aaabb”, “aa”, “aabbb”, and so on.  You may have noticed that q2 is a “trap state”. We can achieve the same effect with the following FSA, where all the transitions to the trap state have been removed — the FSA can reject the input as soon as a non-existent transition is needed.  Like an FSA, each [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) represents a [*language*](http://csfieldguide.org.nz/appendices/Glossary.html#term-language), which is just the set of all [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that match the regular expression. In the example above, the shortest[*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) in the language is “aabb”, then there’s “aaaabb” and “aabbbb”, and of course an infinite number more. There’s also an infinite number of [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) that *aren’t* in this language, like “a”, “aaa”, “aaaaaa” and so on. In the above example, the FSA is a really easy way to check for the [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) — you can write a very fast and small program to implement it (in fact, it’s a good exercise: you typically have an array or list with an entry for each state, and each entry tells you which state to go to next on each character, plus whether or not it’s a final state. At each step the program just looks up which state to go to next.) Fortunately, *every* [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) can be converted to an FSA. We won’t look at the process here, but both Exorciser and JFLAP can do it for you anyway (see the activities below). This is also built into most programming languages. Programmers usually use regular expressions by calling functions or methods that are passed the regex and the[*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) to be searched. But behind the scenes, the [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) is converted to a finite state automaton, and then the job of checking your [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) is very easy. ### 12.4.2\. ACTIVITY: DESIGNING REGULAR EXPRESSIONS[](http://csfieldguide.org.nz/FormalLanguages.html#activity-designing-regular-expressions "Permalink to this headline") Here are some ideas for regular expressions for you to try to create. You can check them using [Rubular](http://rubular.com/) as we did earlier, but you’ll need to make up your own text to check. When testing your expressions, make sure that they not only accept correct strings, but reject ones that don’t match, even if there’s just one character missing. You may find it easier to have one test match [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) per line in “Your test string”. You can force your [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) to match a whole line by putting “^” (start of line) before the regular expression, and “$” (end of line) after it. For example, “^a+$” only matches lines that have nothing but “a”s on them. Here are some challenges to try to create regular expressions for: * local forms of non-personalised number plates (e.g. AB1234 or ABC123 in New Zealand) * any extended form of the word “hello”, e.g. “helloooooooooooo” * variants of “aaaarrrrrgggggghhhh” * a 24-hour clock time (e.g. 23:00) or a 12-hour time (e.g. 11:55 pm) * a bank account or credit card number * a credit card expiry date (must have 4 digits e.g 01/15) * a password that must contain at least 2 digits * a date * a phone number (choose your format e.g. mobile only, national numbers, or international) * a dollar amount typed into a banking website, which should accept various formats like “$21.43”, “$21”, “21.43”, and “$5,000”, but not “21$”, “21.5”, “5,0000.00”, and “300$”. * acceptable identifiers in your programming language (usually something like a letter followed by a combination of letters, digits and some punctuation symbols) * an integer in your programming language (allow for + and - at the front, and some languages allow suffixes like L, or prefixes like 0x) * an IP address (e.g. 172.16.5.2 or 172.168.10.10:8080) * a MAC address for a device (e.g. e1:ce:8f:2a:0a:ba) * postal codes for several countries e.g. NZ: 8041, Canada: T2N 1N4, US: 90210 * a (limited) http URL, such as “[http://abc.xyz](http://abc.xyz/)”, “[http://abc.xyz#conclusion](http://abc.xyz/#conclusion)”, “[http://abc.xyz?search=fgh](http://abc.xyz/?search=fgh)”. ### 12.4.3\. PROJECT: CONVERTING REGULAR EXPRESSIONS TO FSAS[](http://csfieldguide.org.nz/FormalLanguages.html#project-converting-regular-expressions-to-fsas "Permalink to this headline") For this project you will make up a regular expression, convert it to an FSA, and demonstrate how some [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) are processed. There’s one trick you’ll need to know: the software we’re using doesn’t have all the notations we’ve been using above, which are common in programming languages, but not used so much in pure formal language theory. In fact, the only ones available are: * a* matches 0 or more repetitions of a * a|b matches a or b * (aa|bb)* Parentheses group commands together; in this case it gives a mixture of pairs of “a”s and pairs of “b”s. Having only these three notations isn’t too much of a problem, as you can get all the other notations using them. For example, “a+” is the same as “aa*”, and “\d” is “0|1|2|3|4|5|67|8|9”. It’s a bit more tedious, but we’ll mainly use exercises that only use a few characters. #### 12.4.3.1\. CONVERTING WITH EXORCISER[](http://csfieldguide.org.nz/FormalLanguages.html#converting-with-exorciser "Permalink to this headline") Use this section if you’re using Exorciser; if you’re using JFLAP then skip to [`](http://csfieldguide.org.nz/FormalLanguages.html#id8)Converting with JFLAP`~. Exorciser is very simple. In fact, unless you change the default settings, it can only convert regular expressions using two characters: “a” and “b”. But even that’s enough (in fact, in theory any input can be represented with two characters — that’s what binary numbers are about!) On the plus side, Exorciser has the empty [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) symbol available — if you type “e” it will be converted to ϵ. So, for example, “(a| ϵ)” means an optional “a” in the input. To do this project using Exorciser, go to the start (“home”) window, and select the second link, “Regular Expression to Finite Automata Conversion”. Now type your[*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) into the text entry box that starts with “R =”. As a warmup, try: ~~~ aabb ~~~ then click on “solve exercise” (this is a shortcut — the software is intended for students to create their own FSA, but that’s beyond what we’re doing in this chapter). You should get a very simple FSA! To test your FSA, right-click on the background and choose “Track input”. Now try some more complex regular expressions, such as the following. For each one, type it in, click on “solve exercise”, and then track some sample inputs to see how it accepts and rejects different strings. ~~~ aa*b a(bb)* (bba*)* (b*a)*a ~~~ Your project report should show the regular expressions, explain what kind of [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) they match, show the corresponding FSAs, show the sequence of states that some sample test [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) would go through, and you should explain how the components of the FSA correspond the parts of the [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) using examples. #### 12.4.3.2\. CONVERTING WITH JFLAP[](http://csfieldguide.org.nz/FormalLanguages.html#converting-with-jflap "Permalink to this headline") If you’re using [JFLAP](http://www.jflap.org/) for your project, you can have almost any character as input. The main exceptions are “*”, “+” (confusingly, the “+” is used instead of “|” for alternatives), and ”!” (which is the empty [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) — in the preferences you can choose if it is shown as λ or ϵ). So the main operators available in JFLAP are: * a* matches 0 or more repetitions of a * a+b matches a or b * (aa+bb)* Parentheses group commands together; in this case it gives a mixture of pairs of “a”s and pairs of “b”s. The JFLAP software can work with all sorts of formal languages, so you’ll need to ignore a lot of the options that it offers! This section will guide you through exactly what to do. There are some details about the format that JFLAP uses for regular expressions in the following tutorial — just read the “Definition” and “Creating a regular expression” sections. [http://www.jflap.org/tutorial/regular/index.html](http://www.jflap.org/tutorial/regular/index.html) As a warmup, we’ll convert this regex to an FSA: ~~~ ab*b ~~~ On the main control window of JFLAP click on “Regular Expression”, and type your [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) into JFLAP:  From the “Convert” menu choose “Convert to NFA”. This will only start the conversion; press the “Do all” button to complete it (the system is designed to show all the steps of the conversion, but we just want the final result). For the example, we get the following non-deterministic finite automaton (NFA), which isn’t quite what we want and probably looks rather messy:  We need a DFA (deterministic FA), not an NFA. To convert the NFA to a DFA, press the “Export” button, then from the “Convert” menu, choose “Convert to DFA”, press the “Complete” button to complete the conversion, and then the “Done?” button, which will put it in a new window:  We’re nearly there. If it’s hard to read the FSA, you can move states around by choosing the arrow tool (on the left of the tool bar — if the states won’t move when you grab them, so make sure you click on the arrow icon before trying to move them). The states may have some extraneous labels underneath them; you can hide those by selecting the arrow tool, right-click on the white part of the window and un-check “Display State Labels”.  If the FSA is simple enough, it may be just as easy if you now copy the diagram by hand and try to set it out tidily yourself, otherwise you can save it as an image to put into your project. Now try some sample inputs. The starting state is labeled q0 and will have a large arrow pointing at it. You can get JFLAP to run through some input for you by using the “Input” menu. “Step by state” will follow your input state by state, “Fast run” will show the sequence of states visited for your input, and “Multiple run” allows you to load a list of [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) to test. Multiple runs are good for showing lots of tests on your regular expression:  For example, “ab” is rejected because it would only get to state 2. Now you should come up with your own regular expressions that test out interesting patterns, and generate FSA’s for them. In JFLAP you can create FSAs for some of regular expressions we used earlier, such as (simple) dates, email addresses or URLs. Your project report should show the regular expressions, explain what kind of [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) they match, show the corresponding FSAs, show the sequence of states that some sample test [*strings*](http://csfieldguide.org.nz/appendices/Glossary.html#term-strings) would go through, and you should explain how the components of the FSA correspond to the parts of the [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) using examples. ### 12.4.4\. OTHER IDEAS FOR PROJECTS AND ACTIVITIES[](http://csfieldguide.org.nz/FormalLanguages.html#other-ideas-for-projects-and-activities "Permalink to this headline") Here are some more ideas that you could use to investigate regular expressions: * On the [regexdict site](http://www.visca.com/regexdict/), read the instructions on the kinds of [*pattern matching*](http://csfieldguide.org.nz/appendices/Glossary.html#term-pattern-matching) it can do, and write regular expressions for finding words such as: > > > * words that contain “aa” > * all words with 3 letters > * all words with 8 letters > * all words with more than 8 letters > * words that include the letters of your name > * words that are made up *only* of the letters in your name > * words that contain all the vowels in reverse order > * words that you can make using only the notes on a piano (i.e the letters A to G and a to g) > * words that are exceptions to the rule “i before e except after c” — make sure you find words like “forfeit” as well as “science”. > > * Microsoft Word’s *Find* command uses regular expressions if you select the “Use wildcards” option. For more details see [Graham Mayor](http://word.mvps.org/AboutMVPs/graham_mayor.htm)‘s [Finding and Replacing Characters using Wildcards](http://word.mvps.org/FAQs/General/UsingWildcards.htm). * Explore regular expressions in spreadsheets. The Google docs spreadsheet has a function called RegExMatch, RegExExtract and RegExReplace. In Excel they are available via Visual Basic. * Knitting patterns are a form of regular expression. If you’re interested in knitting, you could look into how they are related through the [article about knitting and regular expressions at CS4FN site](http://www.cs4fn.org/regularexpressions/knitters.php). * The Chesapeake NetCraftsmen site provides [a system for practising writing regular expressions](http://www.netcraftsmen.net/presos/Regex_Practice/player.html). * The “grep” command is available in many command line systems, and matches a [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) in the command with lines in an input file. (the name comes from “Global Regular Expression Parser”). Demonstrate the grep command for various regular expressions. * Functions for matching against regular expressions appear in most programming languages. If your favourite language has this feature, you could demonstrate how it works using sample regular expressions and strings. * Advanced: The free tools *lex* and *flex* are able to take specifications for regular expressions and create programs that parse input according to the rules. They are commonly used as a front end to a compiler, and the input is a program that is being compiled. You could investigate these tools and demonstrate a simple implementation. ## 12.5\. GRAMMARS AND PARSING[](http://csfieldguide.org.nz/FormalLanguages.html#grammars-and-parsing "Permalink to this headline") Warning this section hasn’t been written yet; the material below is just an introduction With unusual [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) Yoda from Star Wars speaks. Yet still understand him, people can. The flexibility of the rules of English [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) mean that you can usually be understood if you don’t get it quite right, but it also means that the rules get very complicated and difficult to apply. Grammars in formal languages are much more predictable than grammars in human languages — that’s why they’re called formal languages! When you’re doing English, [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) can be a tricky topic because not only are there are so many rules, but there are also so many exceptions — for example, you need an apostrophe if you write “the computer’s USB port”, but you have to leave it out if you say “its USB port”. Grammars in computer science are mainly used to specify programming languages and file formats, and compilers make a fuss even if you leave out just one bracket or comma! But at least they’re predictable. In this section we’ll look at the kind of grammars that are widely used in computer science. They are very powerful because they allow a complicated system (like a compiler or a format like HTML) to be specified in a very concise way, and there are programs that will automatically take the [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) and build the system for you. The grammars for conventional programming languages are a bit too unwieldy to use as initial examples (they usually take a few pages to write out), so we’re going to work with some small examples here, including parts of the grammars for programming languages. Note: the remainder of this section will be developed during 2013. ### 12.5.1\. PROJECT IDEAS[](http://csfieldguide.org.nz/FormalLanguages.html#project-ideas "Permalink to this headline") (Note that these will make more sense when the previous introduction to grammars has been completed!) * Demonstrate how compilers, interpreters, parsers or validators find errors in formal languages e.g. introduce an error to a compiled program, XML document file or web page, and show the effect of the error. * Find a [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) for a programming language, and show how a sample program would be parsed using the grammar. * Use examples to show the [*parse tree*](http://csfieldguide.org.nz/appendices/Glossary.html#term-parse-tree) (or [*syntax*](http://csfieldguide.org.nz/appendices/Glossary.html#term-syntax) tree) for a correct and incorrect program fragment, or to show a sequence of [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) productions to construct a correct program fragment * Explore the [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) for balanced parentheses S -> SS, S -> (S), S -> ( ) * Find a [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) for a simple arithmetic expression in a programming language, and show the [*parse tree*](http://csfieldguide.org.nz/appendices/Glossary.html#term-parse-tree) for sample expressions (such as (a+b)*(c-d) ). ### 12.5.2\. PROJECTS: GRAMMARS IN ART AND MUSIC[](http://csfieldguide.org.nz/FormalLanguages.html#projects-grammars-in-art-and-music "Permalink to this headline")  The *context free art* program ( [http://www.contextfreeart.org/](http://www.contextfreeart.org/) ) enables you to specify images using a context-free grammar. For example, the following pictures of trees are defined by just a few rules that are based around a forest being made of trees, a tree being made of branches, and the branches in turn being made of branches themselves! These simple definitions can create images with huge amounts of detail because the drawing process can break down the [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) into as many levels as required. You can define your own grammars to generate images, and even make a movie of them being created, like the one below. Of course, if you do this as a project make sure you understand how the system works and can explain the formal language behind your creation. The JFLAP program that we have been using also has a feature for rendering “L-systems” ([http://en.wikipedia.org/wiki/L-system](http://en.wikipedia.org/wiki/L-system)), which are another way to use grammars to create structured images. You’ll need to read about how they work in the JFLAP tutorial (www.jflap.org/tutorial/index.html), and there’s a more detailed tutorial at [http://www.cs.duke.edu/csed/pltl/exercises/lessons/20/L-system.zip](http://www.cs.duke.edu/csed/pltl/exercises/lessons/20/L-system.zip). There are some sample files here to get you inspired: (the ones starting “ex10...” www.cs.duke.edu/csed/jflap/jflapbook/files/ ) and here’s an example of the kind of image that can be produced:  A tree drawn using L-systems in JFLAP There’s also an online system for generating images with L-systems: [http://www.kevs3d.co.uk/dev/lsystems/](http://www.kevs3d.co.uk/dev/lsystems/) Grammars have been used for music notation: * The following is the BNF [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) for the ABC music format: [http://www.norbeck.nu/abc/bnf/abc20bnf.htm](http://www.norbeck.nu/abc/bnf/abc20bnf.htm) * [http://abc.sourceforge.net/](http://abc.sourceforge.net/) * [https://meta.wikimedia.org/wiki/Music_markup](https://meta.wikimedia.org/wiki/Music_markup) * [http://www.emergentmusics.org/theory/15-implementation](http://www.emergentmusics.org/theory/15-implementation) * analyse a simple piece of music in terms of a formal grammar. ## 12.6\. THE WHOLE STORY! If you found the material in this chapter interesting, here are some topics that you might want to look into further, as we’ve only just scratched the surface of what can be done with formal languages. Formal languages come up in various areas of computer science, and provide invaluable tools for the computer scientist to reduce incredibly complex systems to a small description, and conversely to create very complex systems from a few simple rules. They are essential for writing compilers, and so are activated every time someone writes a program! They are also associated with automata theory and questions relating to computability, and are used to some extent in natural language processing, where computers try to make sense of human languages. Technically the kind of finite state automata (FSA) that we used in [Finite state automata](http://csfieldguide.org.nz/FormalLanguages.html#finite-state-automata) section is a kind known as a *Deterministic Finite Automata* (DFA), because the decision about which transition to take is unambiguous at each step. Sometimes it’s referred to as a *Finite State Acceptor* because it accepts and rejects input depending on whether it gets to the final state. There are all sorts of variants that we didn’t mention, including the Mealy and Moore machines (which produce an output for each each transition taken or state reached), the nested state machine (where each state can be an FSA itself), the non-deterministic finite automata (which can have the same label on more than one transition out of a state), and the lambda-NFA (which can include transitions on the empty string, λ). Believe it or not, all these variations are essentially equivalent, and you can convert from one to the other. They are used in a wide range of practical situations to design systems for processing input. However, there are also more complex models of computation such as the push-down automaton (PDA) which is able to follow the rules of context-free grammars, and the most general model of computation which is called a Turing machine. These models are increasingly complicated and abstract, and structures like the Turing machine aren’t used as physical devices (except for fun), but as a tool for reasoning about the limits on what can be computed. The Turing machine is named after Alan Turing, who worked on these concepts in the early 20th century (that’s the same person from whom we got the Turing test in AI, which is something quite different — Turing’s work comes up in many areas of computer science!) If you want to investigate the idea of a Turing machine and you like chocolate, there’s [an activity on the cs4fn site](http://www.cs4fn.org/turing/turingmachines.php) that gives examples of how it works. The Kara programming environment also has a [demonstration of Turing machines](http://www.swisseduc.ch/compscience/karatojava/turingkara/) This chapter looked at two main kinds of formal language: the [*regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) (RE) and the context-free [*grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) (CFG). These typify the kinds of languages that are widely used in compilers and file processing systems. Regular expressions are good for finding simple patterns in a file, like identifiers, keywords and numbers in a program, or tags in an HTML file, or dates and URLs in a web form. Context-free grammars are good when you have nested structures, for example, when an expression is made up of other expressions, or when an “if” statement includes a block of statements, which in turn could be “if” statements, ad infinitum. There are more powerful forms of grammars that exist, the most common being context-sensitive grammars and unrestricted grammars, which allow you to have more than one non-terminal on the left hand side of a production; for example, you could have xAy → aBb, which is more flexible but a lot harder to work with. The relationships between the main kinds of grammars was described by the linguist Noam Chomsky, and is often called the [*Chomsky Hierarchy*](http://csfieldguide.org.nz/appendices/Glossary.html#term-chomsky-hierarchy) after him. There is a direct correspondence between the “machines” (such as the FSA) and languages (such as the Regular Expression), as each increasingly complex language needs the correspondingly complex machine to process it. For example, an FSA can be used to determine if the input matches a given Regular Expression, but a PDA is needed to match a [*string*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) to a CFG. The study of formal languages looks at these relationships, and comes up with ways to create the appropriate machines for a given language and vice versa. There are many tools available that will read in the specification for a language and produce another program to parse the language; some common ones are called “Lex” and “Flex” (both perform lexical anaylsis of regular expressions), “Yacc” (“yet another compiler compiler”) and “Bison” (an improved version of Yacc). These systems make it relatively easy to make up your own programming language and construct a compiler for it, although they do demand quite a range of skills to get the whole thing working! So we’ve barely got started on what can be done with formal languages, but the intention of this chapter is to give you a taste of the kind of structures that computer scientists work with, and the powerful tools that have been created to make it possible to work with infinitely complex systems using small descriptions. ## 12.7\. GLOSSARY[](http://csfieldguide.org.nz/FormalLanguages.html#glossary "Permalink to this headline") Here’s a list of the main terms and concepts that come up in this chapter. [*Alphabet*](http://csfieldguide.org.nz/appendices/Glossary.html#term-alphabet) [*String*](http://csfieldguide.org.nz/appendices/Glossary.html#term-string) [*Finite state automaton*](http://csfieldguide.org.nz/appendices/Glossary.html#term-finite-state-automaton) [*Regular expression*](http://csfieldguide.org.nz/appendices/Glossary.html#term-regular-expression) [*Pattern matching*](http://csfieldguide.org.nz/appendices/Glossary.html#term-pattern-matching) [*Lexical analysis*](http://csfieldguide.org.nz/appendices/Glossary.html#term-lexical-analysis) [*Grammar*](http://csfieldguide.org.nz/appendices/Glossary.html#term-grammar) [*Parsing*](http://csfieldguide.org.nz/appendices/Glossary.html#term-parsing) [*Parse tree*](http://csfieldguide.org.nz/appendices/Glossary.html#term-parse-tree) [*Syntax*](http://csfieldguide.org.nz/appendices/Glossary.html#term-syntax) [*Syntax diagram*](http://csfieldguide.org.nz/appendices/Glossary.html#term-syntax-diagram) [*Syntactically correct*](http://csfieldguide.org.nz/appendices/Glossary.html#term-syntactically-correct) [*Chomsky hierarchy*](http://csfieldguide.org.nz/appendices/Glossary.html#term-chomsky-hierarchy) ## 12.8\. FURTHER READING[](http://csfieldguide.org.nz/FormalLanguages.html#further-reading "Permalink to this headline") Some of the material in this chapter was inspired by [http://www.ccs3.lanl.gov/mega-math/workbk/machine/malearn.html](http://www.ccs3.lanl.gov/mega-math/workbk/machine/malearn.html) There’s a good article on finite state machines at [http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html](http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html) Textbooks on formal languages will have considerably more advanced material and more mathematical rigour than could be expected at High School level, but for students who really want to read more, a popular book is “Introduction to the Theory of Computation” by Michael Sipser. Regular expressions and their relationship with FSAs is explained well in the book “Algorithms” by Robert Sedgewick. ### 12.8.1\. USEFUL LINKS[](http://csfieldguide.org.nz/FormalLanguages.html#useful-links "Permalink to this headline") * [http://en.wikipedia.org/wiki/Formal_language](http://en.wikipedia.org/wiki/Formal_language) * [http://en.wikipedia.org/wiki/Context-free_grammar#Examples](http://en.wikipedia.org/wiki/Context-free_grammar#Examples) * [http://en.wikipedia.org/wiki/Abstract_syntax_tree](http://en.wikipedia.org/wiki/Abstract_syntax_tree) * [http://en.wikipedia.org/wiki/Regular_expression](http://en.wikipedia.org/wiki/Regular_expression) * [http://csunplugged.org/finite-state-automata](http://csunplugged.org/finite-state-automata) * [http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html](http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html) * [http://www.jflap.org/](http://www.jflap.org/) * [http://en.wikipedia.org/wiki/Deterministic_finite_automaton](http://en.wikipedia.org/wiki/Deterministic_finite_automaton) * [http://en.wikipedia.org/wiki/Finite-state_machine](http://en.wikipedia.org/wiki/Finite-state_machine)