Paul’s ComSci Wafflings

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 »

The Java API contains numerous classes for managing collections (or sets) of objects. A collection allows us to easily model a large number of data values or objects. There are four main types of collections which are available through various API packages; firstly lists. A list is an ordered collection of objects, we’d use this where the order elements appear in a list is meaningful (such as modeling a queue, or ordered list of items). A set is an unordered collection of objects, in which each element may only appear once (as per the normal rules of Set Theory). A stack is a collection type where elements are only added and removed from the front of the list, for example maintaining a list of recent events where the topmost item is always the most recent. Finally, a map is a collection of data pairings, where an element from a data collection is paired with an element from a key collection - for example pairing works (keys) to their definitions (data).

Read the rest of this entry »

A proof aims to establish a fact by taking a proposition - conjecture - and applying by the mathematical axioms (given truths) establish a proved theorum. Induction is a general method for establishing a proof, and is usually used to establish that a proposition is true for any natural number.

Read the rest of this entry »

A set is a collection of distinct objects considered as a whole.

[Wikipedia - http://en.wikipedia.org/wiki/Set ]

A set can be thought of as a collection of objects - or elements - and these objects can be anything, data - numerical - or indeed other sets. Elements in a set are in no particular order, and elements in a set must by definition be unique.

Read the rest of this entry »

A Proposition is a declarative sentence, which may be shown to be either true, or false, whether the statement is true or false is not - however - relevant. Both “1+2-=3″ and “1+2=4″ are example of propositions. Predicate logic allows us to explore the truthfulness of a statement, it has an expressive power which propositional logic does not.

Read the rest of this entry »

The application layers  provides applications with access to the communications environment. A network-enabled application will create a user interface as well as interfacing with application layer network protocols.

Read the rest of this entry »

“A network is a system or group of interconnected elements. A computer network is a group of computers and peripherals connected together to communicate with each other and to share information and resources.”

http://www.micro2000.co.uk/network_glossary.htm
Read the rest of this entry »