# Finite Automata with Output.

Finite Automata is the important topic of the Theory Of Computation. Theory Of Computation is the Important subject of the Computer.

Finite automata have limited capability of either accepting a string or rejecting a string.

Acceptance of string was based on the reachability of a machine from starting state to final state. Finite automata can also be used as an output device.

Such machines do not have a final state.

The machine generates output on every input.

There are two types of automata with outputs:

- Moore machine
- Mealy machine

## Procedure to Minimize Finite Automata

** ^{ }S-1**: Make final state and non-final state as distinguish.

**S-2**: Recursively interacting over the pairs of state for any transition for

δ(p,x) = r, δ(q,x) = sand for x ∈ ε. If rand s are distinguishable make p and q as distinguish.

**S-3**: If any iteration over all possible state pairs one fails to find a new pair of states that are distinguishable terminate.

**S-4**: All the states that are not distinguished are an equivalence.

### Pumping Lemma and its Application

** ^{ }**Suppose L is a regular language. Then there is an integer n so that for any x∈ L with |x|>=n, there are strings u, v, and w so that

x=uvw

|uv|<=n

|v|>0

For any m>=0, uv^{m}w ∈ L

**Application: (****Explain the application of the Pumping Lemma to show a Language is Regular or Not) **The pumping lemma is extremely useful in proving that certain sets are non-regular. The general methodology followed during its applications is :

Select a string z in the language L.

Break the string z into x, y and z in accordance with the above conditions imposed by the pumping lemma.

Now check if there is any contradiction to the pumping lemma for any value of i.

**Related Terms**

Theory of Computation, NFA With ^-Transition, Regular Language, Pushdown Automata

## Leave a Reply