Operations That Can Be Performed on Languages

Concatenation
L₁ . L₂ = L₁L₂ = {w ε Σ| w=xy for some x ε L₁ and y ε L₂}

Closure (pairing of elements)
examples:
L₁ = {a}
L₁* = {e,a,aa,aaa,aaaa,...}
L₂ = {aa, bb}
L₂* = {e,aa, bb,aaaa,aabb,bbaa,bbbb,...}
L₃ = 0
L₃* = {e}
(note: * is Kleene's Star and e represents empty)

Positive Closure Property
L⁺ = LL*
example:
L = {aa,bb}
L* = {e,aa,bb,aaaa,aabb,bbaa,bbbb,...}
L⁺ = {aa,bb,aaaa,aabb,bbaa,bbbb,...}
Elements of L are concatenated with the elements of L*.

Union
L = L₁ ∪ L₂
example:
L₁ = {a}
L₂ = {b}
L₁ ∪ L₂ = {a,b}

Intersection
L = L₁ ∩ L₂
example:
L₁ = {a,b}
L₂ = {b}
L₁ ∩ L₂ = {b}

Difference
L = L₁ - L₂
example:
L₁ = {a,b}
L₂ = {b}
L₁ - L₂ = {a}

Complement
~L = Σ* - L

Read More ..

OSI Layers

src:http://en.wikipedia.org/wiki/OSI_model

The Open Systems Interconnection Reference Model (OSI Reference Model or OSI Model) is an abstract description for layered communications and computer network protocol design.

A layer is a collection of conceptually similar functions that provide services to the layer above it and receives service from the layer below it. On each layer an instance provides services to the instances at the layer above and requests service from the layer below. For example, a layer that provides error-free communications across a network provides the path needed by applications above it, while it calls the next lower layer to send and receive packets that make up the contents of the path.

Short Description of OSI Layers (top to bottom)

Application Layer:
The layer that is closest to the end user. This layer interacts with software applications that implement a communicating component. Some examples of application layer implementations are Telnet, Hypertext Transfer Protocol (HTTP), File Transfer Protocol (FTP), and Simple Mail Transfer Protocol (SMTP).

Presentation Layer:
This layer provides independence from differences in data representation (e.g., encryption) by translating from application to network format, and vice versa. The presentation layer works to transform data into the form that the application layer can accept. This layer formats and encrypts data to be sent across a network, providing freedom from compatibility problems. It is sometimes called the syntax layer.

Session Layer:
It establishes, manages and terminates the connections between the local and remote application. It provides for full-duplex, half-duplex, or simplex operation, and establishes checkpointing, adjournment, termination, and restart procedures.

Transport Layer:
Provides transparent transfer of data between end users, providing reliable data transfer services to the upper layers. The Transport Layer controls the reliability of a given link through flow control, segmentation/desegmentation, and error control. Some protocols are state and connection oriented. This means that the Transport Layer can keep track of the segments and retransmit those that fail.

Network layer:
Provides the functional and procedural means of transferring variable length data sequences from a source to a destination via one or more networks, while maintaining the quality of service requested by the Transport Layer. The Network Layer performs network routing functions, and might also perform fragmentation and reassembly, and report delivery errors. Routers operate at this layer—sending data throughout the extended network and making the Internet possible. This is a logical addressing scheme – values are chosen by the network engineer. The addressing scheme is hierarchical.

Data Link Layer:
Provides the functional and procedural means to transfer data between network entities and to detect and possibly correct errors that may occur in the Physical Layer. Originally, this layer was intended for point-to-point and point-to-multipoint media, characteristic of wide area media in the telephone system.

Physical Layer:
The Physical Layer defines the electrical and mechanical specifications for devices.

Read More ..

Search Engine Tips

• Get to know your search engine if you haven't already discovered it (e.g. google, bing).
• To narrow down your internet search, enclose any search phrases in speech marks. eg: "Melbourne Observer". That way, you'll only get pages with the actual TERM 'Melbourne Observer' appearing. Without the speech marks, you'll get lots of pages with the word 'Melbourne', lots of pages with the term 'Observer', and then pages with the term 'Melbourne Observer'.
• Use a 'plus' sign with any words that MUST appear in the search results. Similarly, use a 'minus' sign with any words that MUST NOT appear in the search results. (There is no space between the symbol and the word) e.g.: "banana bread" +chocolate -sultanas
• When you come across a page that you will be visiting often, make sure you 'bookmark' it by adding it to your list of Favorites. With the page displayed, simply go up to the Favorites menu (yes, the US spelling!) and choose 'Add to Favorites'. If you are like me and you have an endless list, it would be a good idea to sort them into Folders, too.
• When you have done a search using a search engine like google and you're presented with a long list of pages you'd like to check out, this tip will help you do that without losing the original list: RIGHT MOUSE CLICK on the first link you'd like to open and choose from the shortcut menu that appears 'Open Link in New Window'. Some browsers have 'Open Link in New Tab', allowing you to view the contents of the link in the same browser having its own tab below the toolbars.
  

Read More ..

Automata Theory Part 2

Three Kinds of Finite Automata:

Deterministic Finite Automata (DFA)
Each state has a transition for every symbol in the alphabet.

Nondeterministic Finite Automata (NDFA)
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q₀ to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.


Nondeterministic Finite Automata, with ε Transitions
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with ε, then the NFA can be in any of the states reached by the ε-transitions, directly or through other states with ε-transitions. The set of states that can be reached by this method from a state q, is called the ε-closure of q.

Read More ..