Finite Automata with Output.
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
For any m>=0, uvmw ∈ 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.