August 2019

at August 31, 2019 1

Theory Of Computation (TOC) | Eliminating Epsilon Transition(ε-Transitions):

Given any Epsilon NFA (ε-NFA) , we can find a DFA D that accepts the same language as E. The construction is close to the subset construction, as the states of D are subsets of the states of E. The only difference is that dealing with ε-transitions, which can be done by using ε-closure.


Epsilon NFA (ε-NFA) - DFA:
Let E = (QE,∑, 𝛿E,qo, FE) is ε-NFA. The DFA equivalent to given ε-NFA is constructed as:

D = (QD,∑, 𝛿D,qD, FD)

 Where,
QD= set of subsets of QE i.e QD ⊆ 2ᣔQE
qD=ε-closure(qo)
FD = set of states that contains at least one accepting state of E.
i.e. FD= {S|S is in qD and S∩FE∉φ}.
𝛿D (S, a) is computed, for all a in ∑ and sets S in QD by:


  • Let 𝛿cap(q, x) = {p1, p2,......, pk} i.e. pi ’s are the states that can be reached from q following path labeled x which can end with many ε & can have many ε.
  • Compute

  • Then,


For Example:

Conversion of Epsilon-NFA to DFA

Given an ε-NFA as:





Transition Diagram:

ε-NFA —NFA:

Let E = (QE,∑, 𝛿E,qo, FE) is ε-NFA. The NFA equivalent to given ε-NFA is constructed as:
N = (QN,∑, 𝛿N,qN, FN)
  • Start state of NFA =Start state of ε-NFA i.e. qN= qo
  • QN= set of subsets of QE i.e QN ⊆ QE
  • For any state q  ∈ QN and a ∈ Σ:
𝛿N(q, a) = ε-closure (𝛿E(ε- closure(q), a))
  • FN= { q ∈ QN: ε- closure(q) ∩FE≠φ}


For Example:

Given an ε-NFA as:


Transition Table:

Transition Diagram:

Read more »

at August 28, 2019 0

NFA with Epsilon-Transition (ε-NFA) | Epsilon-Closure (ε-Closure) of a state | Extended Transition Function of ε-NFA  | Theory Of Computation (TOC)

NFA with Epsilon(ε) Transition (ε-NFA):

The NFA with epsilon-transition is a finite state machine in which the transition from one state to another state is allowed without any input symbol i.e. empty string ε. Adding the transition for the  empty string doesn’t increase the computing power of the finite automata but adds some flexibility to construct then DFA and NFA. This are very helpful when we study regular expression (RE) and prove the equivalence between class of language accepted by RE and finite automata.


 Formally, ε-NFA is defined by five tuples as:
A = (Q, ∑,𝛿, qo, F),
Where,
Q = set of finite states
∑ = set of finite input symbols
𝛿= a transition fimction that maps: Q✕Z ∪ {ε}→ 2^Q
qo= Initial state, qoЄQ
F = set of final states; F⊆Q

 For Example:-
Fig: ε-NFA accepting the language {a, aa, ab, abb, b, bbb, ................... 

 Transition Table:-


Epsilon-closure (ε-closure) of a state:

The s-closure of a state of ε-NFA is the set of stats those can be eased from that state with s-transition. The a-closure is defined as recursively as:
Basis: state q is in ε-closure (q).
Induction: If state q is reached with s-transition from state q, p is in ε-closure (q). And if there is
an arc from p to r labeled 2, then r is in ε-closure (q) and so on.
For Example:


ε-closure (P) = {p,q,r,s} 
ε-closure (q) = {q, s}
ε-closure (r) = {r} 
ε-closure (s) = {s}  
ε-closure (t) = {t} 
ε-closure (u) = {u,w,y}
ε-closure (v) = {v, x, y}
ε-closure (w) = {w, y}
ε-closure (x) = {x, y}
ε-closure (y) = {y}

Extended Transition Function of ε-NFA:

The extended transition function of ε-NFA denoted by 𝛿cap, is defined as:
Basis: 𝛿cap(q, e) = ε-closure (q)

Induction:
Let w = xa be a string, where x is substring of w without last symbol a and a ∈ E but a≠ε.

Let 𝛿cap(q, x) = {p1, p2,...., pk} i.e. pi are the states that can be reached from q following path labeled x which can end with many ε & can have many ε.

Also let,

Then,

Example:

Compute for string ba
𝛿cap(p, 2) = e-closure (p) = {p, q, r, u}

Compute for b
𝛿(p, b)∪ 𝛿(q, b) ∪ 𝛿(r, b) ∪ 𝛿(u, b) = {s, v)
ε-colsure (s) ∪ ε-closure (v) = {s, t, v}

Compurerfor next input a
𝛿(s, a) ∪ 𝛿(t, a) ∪ 𝛿(v, a) = {y, w}
ε-closure (y) ∪ ε-closure (w) = { y, w}
The final result set contains the one of the final state so the string is accepted.

Related Posts:-

Read more »

at August 27, 2019 0

Computer Network

According to Tanenbaum, computer network is a collection of ―autonomous‖ computers interconnected by a single technology. It is a collection of computers and other devices interconnected by communication channels that allow sharing of resources and information. The connection can be done as peer-to-peer or client/server.


Basic Elements of a Network:

•        Data
a  collection of known facts and figures that can be represented and transferred in an electronic format, e.g. text, numbers, pictures, audio, video
•        Sender
a  collection of User and Hardware, e.g. a computer
•        Receiver
a  collection of User and Hardware, e.g. a computer
•        Medium
the channel or path through which the data transfers, e.g. cable
•        Protocol
system of digital message formats and rules for exchanging those messages

Applications of Computer Networks:

•        Business Applications (Electronic Inventory, Information Systems, Email, Accounting/Payroll, OLTP, MIS/Reporting, Online Database, etc)
•        Home Applications (Communication, Gaming, Ecommerce, Remote Sharing)
•        Mobile Users (24x7 Online, GPS / Location tracking, Instant communication)

Advantages and Disadvantages of Computer Networks:

Advantage:

•        Communication
•        Sharing of files, data, and other types of information
•        Sharing of network and computing resources
•        Increased Storage Capacity
•        Increased Performance
•        Increased Cost Efficiency
•        Increased Fault Tolerance / High Availability

Disadvantage:

•        Security Issues
•        Threat of Computer Viruses
•        Dependency
•        Interference with other technologies
•        Expensive and difficult Setup
•        Legal and Social Issues

Networks may be classified according to a wide variety of characteristics such as:

•        Scale / Span of the network
•        Topology the network follows,
•        Medium used to transport the data,
•        communications Protocol used,
•        organizational Scope



Types of Network according to Physical Span:


Local Area Network (LAN)

A LAN connects network devices over a relatively short distance. A networked office building, school, or home usually contains a single LAN, though sometimes one building will contain a few small LANs (perhaps one per room), and occasionally a LAN will span a group of nearby buildings. In TCP/IP networking, a LAN is often but not always implemented as a single IP subnet. 
In addition to operating in a limited space, LANs are also typically owned, controlled, and managed by a single person or organization. They also tend to use certain connectivity technologies, primarily Ethernet and Token Ring. 
Most local area networks are built with relatively inexpensive hardware such as Ethernet cables, network adapters, and hubs. Some of the major technologies that the LANs use are Ethernet, Token Ring, FDDI, WiFi, etc.

Metropolitan Area Network (MAN)

A metropolitan area network (MAN) is a computer network that usually spans a city or a large campus. A MAN usually interconnects a number of local area networks (LANs) using a high-capacity backbone technology, such as fiber-optical links, and provides up-link services to wide area networks (or WAN) and the Internet. An example of MAN can be the Cable Television broadcasting.
Some technologies used for this purpose are Asynchronous Transfer Mode (ATM), FDDI, and SMDS, however, they are in the verse of being replaced by the Ethernet based MAN, also known as Metro-Ethernet. MAN can also use wireless technologies like microwave, radio, or infra-red laser links

Wide Area Networks (WAN)

WAN spans a large physical distance. It is a geographically-dispersed collection of LANs. A network device called a router connects LANs to a WAN. In IP networking, the router maintains both a LAN address and a WAN address. The Internet is the largest WAN, spanning the Earth.
A WAN differs from a LAN in several important ways. Most WANs (like the Internet) are not owned by any one organization but rather exist under collective or distributed ownership and management. WANs tend to use technology like ATM, Frame Relay and X.25 for connectivity over the longer distances. 




Read more »

at August 25, 2019 0

Non Deterministic Finite Automata (NFA):

Like the DFA, a NFA has a finite set of states, a finite set of input symbols, one start state, a set of accepting states and transition function (𝛿). The difference between the DFA and the NFA is in the type of 𝛿. For the NFA, 𝛿 is a function that takes a state and input symbol as arguments as like the DFA’s transition function, but returns a set of zero, one or more state (DFA returns exactly one state).

Formal Definition

A non deterministic finite automaton is a quintuple A: (Q, ∑, 𝛿, qn, F), where
Q = finite set of states.
∑= finite set of input symbols.
𝛿= transition function that maps Q✕∑→2^ Q
qo = a member of Q, is the start state.
F = a subset of Q, is the set of final states.

 Adding the non-determinism to finite state machine doesn’t increase the power of computability, but it makes flexible to construct finite state machine to represent the language. So. the computation power of DFA and NFA is not different, only to construct a NFA is easier than DFA.

 For example:
Fig: NFA accepting all strings that end on 01

Here, from state q, there is no any arc for input symbol 0 & no any arc out of Q3 for 0 & l. So, we can conclude in a NFA, there may be zero no. of arcs out of each state for each input symbol.While in DFA, it has exactly one arc out of each state for each input symbol.
Fig: Transition table for NFA accepting all strings that end on 01


  • NFA over {0, 1} accepting strings {0, 01, 11}.
  • Transition Table:

Computation tree for 01;
Computation tree for 01 10;

The computation tree of the processing of any string by an NFA represents the entire path from start state that can follow by an NFA for processing that string. The root of tree is the start state. After completing the tree for a string of length ‘n’, if there is any final state node at level ‘n’, then the NFA accepts that string otherwise doesn’t.
In above example,
|01|= 2
At level 2, there is 21 final state node (q2). So, 01 is accepted by a NFA.


The Extended transition function of NFA:

As for DFA’s, we need to define the extended transition function 𝛿 that takes a state q and a string of input symbol w and returns the set of states that is in if it starts in state q and processes the string w.

Definition by Induction:
Basis Step: Then, 𝛿cap (q, a) = {q} i.e. reading no input symbol remains into the same state.
Induction: Let w be a string from ∑* such that w = xa, where x is a substring of without last symbol a. Also, Suppose that,
𝛿cap(q, x) = {p1,p2,p3,....,pt}
Let,

Then, 𝛿cap(q, w) = {r1,r2,  ....,rm}
We compute  𝛿cap(q, w) by first computing 𝛿cap(q, x) and then following any transition from any of these states that is labeled a.

Let us consider a NFA accepting all strings that end on 01:

Here, we use 𝛿cap to describe how the string 00101 is processed by the NFA.


Language of NFA:

The language of NFA, A = (Q, ∑,𝛿, qo, F), denoted by L (A):
L(A)= {w|𝛿cap(q,w)  F≠φ}
i.e. L(A) is the set of strings W in ∑* such that 𝛿cap(qo,w) contains at least one state accepting state.

Related Posts:-

Read more »

at August 23, 2019 0

Automata Theory

Automata (singular: automation) are abstract models of machines that perform computations on an input by moving through a series of states. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present state. As a result, once the computation reaches an accepting state, it accepts that input. The most general and powerful automata is the Turing machine.


Characteristics of such machines include:

  • Inputs: assumed to be sequences of symbols selected from a finite set I. Namely, set I is the set {x1, x,2. x3,...,xk} where k is the number of inputs.
  • Outputs: sequences of symbols selected from a finite set Z. Namely, set Z is the set {y1,y2, y3,....,ym} where m is the number of outputs.
  • States: finite set Q, whose definition depends on the type of automaton. 

An automaton has a mechanism to read input, which is string over a given alphabet. This input is actually written on an input tape /file, which can be read by automaton but cannot change it.
Input file is divided into cells each of which can hold one symbol. Automaton has a control unit which is said to be in one of finite number of internal states. The automation can change states in
a defined way.

Fig: Diagrammatic representation of a generic automation




There are four major families of automaton:


  • Finite-state machine
  • Pushdown automata
  • Linear-bounded automata
  • Turing machine


The families of automata above can be interpreted in a hierarchical form, where the finite-state machine is the simplest automata and the Turing machine is the most complex. The focus of this project is on the finite-state machine and the Turing machine.

States, Transitions and Finite-State Transition System


A state of a system is an instantaneous description of that system which gives all relevant information necessary to determine how the system can evolve from that point on.

Transitions are changes of states that can occur spontaneously or in response to inputs to the states. Though transitions usually take time, we assume that state transitions are instantaneous (which is an abstraction).

A system containing only a finite number of states and transitions among them is called a finite- state transition system.

Finite State Machines:

An automaton in which the state set Q contains only a finite number of elements is called a finite-state machine (FSM). FSMs are abstract machines, consisting of a set of states (set Q), set of input events (set I), a set of output events (set Z) and a state transition function. The state transition function takes the current state and an input event and returns the new set of output events and the next state. Therefore, it can be seen as a function which maps an ordered sequence of input events into a corresponding sequence, or set, of output events.

In order to fully understand conceptually a finite-state machine, consider an analogy to an elevator:

An elevator is a mechanism that does not remember all previous requests for service but the current floor, the direction of motion (up or down) and the collection of not-yet satisfied requests for services. Therefore, at any given moment in time, an elevator in operated would be defined by the following mathematical terms:


  • States: finite set of states to reflect the past history of the customers’ requests.
  • Inputs: finite set of input, depending on the number of floors the elevator is able to access. We can use the set I, whose size is the number of floors in the building.
  • Outputs: finite set of output, depending on the need for the elevator to go up or down,according to customers‘ needs.


Applications of Finite State Machines


  • Traffic Lights
  • Video Games
  • Text Parsing
  • CPU Controllers
  • Protocol Analysis
  • Natural Language Processing
  • Speech Recognition


Types of Finite Automata:

Finite Automaton can be classified into two types:
Deterministic Finite Automata (DFA)
Non-deterministic Finite Automata (NDFA/ NFA)

Deterministic Finite Automata (DFA)

Deterministic Finite State Automata (DFA) are simple machine that reads an input string- one symbol at a time- and then, after the input has been completely read, decides whether to accept or reject the input. As the symbols are read from the tape, the automata can change its state, to reflect how it reacts to what it has seen so far.

Thus, a DFA conceptually consists of 3 parts:


  • A tape to hold the input string. The tape is divided into a finite number of cells. Each cell holds a symbol from .
  • A tape head for reading symbols from the tape
  • A control , which itself consists of 3 things:
  1. finite number of states that the machine is allowed to be in (zero or more states are designated as accept or final states),
  2. a current state, initially set to a start state,
  3. a state transition function for changing the current state.

An automaton processes a string on the tape by repeating the following actions until the tape head has traversed the entire string:

  • The tape head reads the current tape cell and sends the symbol s found there to the control. Then the tape head moves to the next cell.
  • The control takes s and the current state and consults the state transition function to get the next state, which becomes the new current state.


Once the entire string has been processed, the state in which the automation enters is examined.If it is an accept state, the input string is accepted; otherwise, the string is rejected.


Formal Definition

A deterministic finite automaton is defined by a quintuple (5-tuple): A = (Q, ∑, 𝛿, qo, F).
Where,
Q = Finite set of states,
∑= Finite set of input symbols,
𝛿= A transition function that maps Q X ∑ → Q
qo: A start state; qo∈Q
F= Set of final states; F ⊆ Q.

A transition function 6 that takes as arguments a state, an input symbol and returns a state. In our diagram,  is represented by arcs between states and the labels on the arcs.

If s is a state and a is an input symbol then 𝛿(p,a) is that state q such that there are arcs labeled ‘a’ from p to q.

General Notations of DFA:

There are two preferred notations for describing automata.

  • Transition Diagrams
  • Transition Tables


Transition Diagrams

A transition diagram for a DFA A = (Q, ∑, 𝛿, qo, F). is a graph defined as follow:

  • For each state is node represented by circle.
(q is State)

  • A start stat is represented by a circle with preceding arrow labeled at start.

  • Final state is marked by a double circle
(q is Final State)

  • For each state q in Q and each input a in Z, if 𝛿(q, a) = p then there is an arc from node q to p labeled a in the transition diagram. If more than one input symbol cause the transition from state q top then arc from q to p is labeled by a list of those symbols.

𝛿(q,a)=p


For Example:

Specify a DFA that accepts all and only the strings of 0’s and l’s that have sequence 01 somewhere in the string.
L = {x01y I x and y are any strings of 0’s and l’s}

Fig: The transition diagram for the DFA accepting all strings with a substring 01

Transition Table

A transition table is a conventional, tabular representation of a function 𝛿 that takes two arguments and returns a value. The rows of the table correspond to the states and the columns correspond to the inputs. The entry for the row corresponding to state q and the column corresponding to input a is the state 𝛿( q, a).
The start state is marked with an arrow and the accepting states are marked with a star.

Fig: Transition table for DFA accepting all strings with a substring OI


Extending the Transition Function to Strings:

If 𝛿 is transition function, then the extended transition function constructed from 𝛿, called as 𝛿. The extended transition function is a function that takes a state q and a string w and returns a state p. The state that the automaton reaches when starting in state q and processing the sequences of input w.


Language of DFA:

The language of DFA, A = (Q, ∑, 𝛿, qo, F) denoted by L(A) and defined by:


i.e. the language of a DFA is the set of all strings w that take DFA starting from start state to one of the accepting states. The language of DFA is called regular language.


Related Posts:-


Read more »
Subscribe to: Posts (Atom)