Computation - Patterns

Patterns

In the last blog post we looked at what the various components in the module, mostly languages, symbols, and alphabets.  Now we're going to look in more detail at how to define a language from symbols.

To define languages more easily we're going to look at patterns.  Patterns can also be called regular expressions.  Computers, after all, can't recognise set notation symbols such as {, }, or ∈.

Computation - Sets & Languages

Sets & Languages

In order for a computer to organise a textual input, the computer has to be able to recognise certain strings, such as, in parsing a programming language, it has to be able to find 'if' or 'while'.

The first part of Computation deals with how we describe to a computer what string to look for, how to come up with the right description to solve the problem, and how to do more advanced things such as check whether a piece of code is correctly formed, making sure that opening and closing brackets match, or checking that a webpage is written in valid HTML.

Computation - CFG to DFA

CFGs to DFAs

Hopefully you should remember what a CFG consists of. That is:

• A set of terminal symbols. That is, some given alphabet.


• A set of non-terminal symbols.


• A start state – S.

Computation - Growth Rates and Orders

Growth Rate of Functions

OK, so this post is mainly because some people ‘begged’ me to put it on. From the examples you may have – hopefully? – seen in a previous post – if you haven’t here it is: http://computersciencesource.wordpress.com/2009/09/09/comp10042-computation-time-space-complexity/ .

Computation - Halting Problem

Termination

Let’s take another look at the piece of simple Java code that we looked at earlier:

Computation - Time & Space Complexity

Time is a precious thing

Imagine, if you will, a children’s puzzle game – the Tower of Hanoi. With this, you have to move – say 8 disks – from one post to another. Each disk has to be moved – one at a time – onto another post, provided that the disk – if it exists – that it lands on is not smaller. Continuing on with the 8 disks, to solve such as simple puzzle will take a child 2ⁿ-1moves. So for 8 disks, this will be 255 moves – that’s quite a lot.

Computation - Context-Free Grammars

Well-defined Rules

Instead of thinking of patterns that may be matched by some strings, it is our aim here to generate all the words of some language following so well-defined rules. The way of reading the rules is to see them as way of rewriting the string generated so far. For example, by using the given rules, to change one of the symbols in the current string, into a string of others. Such as, changing ‘S’ in this string to ‘at’:

Computation - Patterns to Automaton

What If?

So, now we’ve seen a way to transform an automaton into a pattern. BUT! How do we go about doing it the other way around? How do we transform a pattern into its counterpart automaton?

Computation - Automaton to Patterns

A brief Summary

So far we have seen 3 ways in which to talk about a language over given alphabet. These are:

1. Set-theory


2. Regular Expressions (patterns)


3. NFAs and DFAs (automatons)

Computation – An NFA to a DFA

Non-Deterministic Finite Automata (NFA)

So now you’ve seen a slight introduction into DFAs, its time to introduce their counterpart – NFAs! Now as seen from above, a DFA can sometimes be relatively simple to draw, however, sometimes it can be even easier to draw an NFA.

Computation - Finite State Automaton (part 2)

Finite State Automata

OK, so that last part was only introducing you to the idea of using automata for expressing patterns in a better, and more meaningful way. However, it is now time to take this to a new and more formal level.

Before we can even think about drawing an automaton, we must know one thing! That is of course the alphabet, Σ. As without an alphabet, an automaton would be pretty darned meaningless!

Computation - Intro to Automaton (part 1)

Using Pictures for Patterns

Imagine if someone told you to check a queue of an unknown length to see if it contained an even number of zombies. How would you do it?

Computation - Regular Expressions

Computers and Sets don’t go

Up till now we’ve only seen how to express languages as sets, such as:

• {(01)n | n Є N}

While we can all understand this, if you go ahead right now and type it into a computer then you’ll just get a lot of evil error messages thrown at you - no, not becuase you're using Windows, but because we have to express the language in a very different way. This way of expressing is known a patterns!

Computation - Sets and Languages

OK, so first things first, we need to settle on some terminology here. This is because things such as symbols can also be cause characters, so I need to mention which terminology will be used here.