Paul Nicholls

Pumping Lemma describes a fundamental property of regular languages, in simple terms it states that in order for a language to be regular, sufficiently long words may be pumped, where pumped means that a given section of the middle of the word, can be repeated a number of times to produce a new word which still lies within the same language.

Formally, Let be a regular language. Then there exists an integer depending only on such that every string in of length at least (the “pumping length”) can be written as (i.e., can be divided into three substrings), satisfying the following conditions:

Why Is This Relevant?

This method can be used to show a language is not regular, since if it meets the above criteria then it must be a regular language, so a proof by contradiction can be used to show which languages are not regular and thus not able to be modelled by NFAs or DFAs.

A nondeterministic finite-state machine (NFA) is not wholly disimilar to a DFA, however unlike a DFA from any pairing of state and input symbol there may be more than one valid next state. An NFA accepts a string of symbol inputs, and for each symbol it transitions to a next state until there are no more symbols. Unlike a DFA however the next state is not determined any may be any state of a given set of states. When all the inputs symbols have been processed, an NFA will accept if any valid set of transitions resulted in an accept state.

Read the rest of this entry »

Deterministic Finite-State Automaton (DFA) are a method of modelling computation, and are used in conjunction with regular languages. In a DFA from each pair of input symbol and state there is only one transition to a next state (so, from any state given an input symbol the next state can be readily determined).

As an input a DFA will expect a string of symbols, each input symbol will cause a transition to a next state, until there are no more input symbols. At this point the DFA will either be on an accept state, or a non accept state – and will return “accept” or “non accept” accordingley.

It follows that the DFA recognises the language if , and where any DFA accepts the langauge , must be a regular lanaguage.

Read the rest of this entry »

We need to define exactly what we mean by a computation (at a much higher level than a line of programming), there are various mathematic models for doing so which we considor in the field of the Theory of Computation. Such examples include the Turing Machine model, push-down automaton and finite-state automaton. (Most though commonly we only considor the Turing Machine model).

In the field of the theory of computation we tend to be concerned with two fields:

• Computability Theory (Whether a problem can actually be solved by computation)
• Complexity Theory (If a problem can be solved, whether it be solved efficiently)

Read the rest of this entry »