Jump to content

Nondeterministic finite automaton with ε-moves

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ashutosh y0078 (talk | contribs) at 10:19, 6 March 2012 (→Properties of NFA-ε). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In the automata theory, a nondeterministic finite automaton with ε-moves (NFA-ε)(also known as NFA-λ) is an extension of nondeterministic finite automaton(NFA), which allows a transformation to a new state without consuming any input symbols. The transitions without consuming an input symbol are called ε-transitions or λ-transitions. In the state diagrams, they are usually labeled with the Greek letter ε or λ.

ε-transitions provides a convenient way of modeling the systems whose current states are not precisely known. ε-transitions does not add any extra capacity of recognizing formal languages. NFA-εs and NFAs recognize same class of formal languages, namely regular languages. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA. Since a NFA-ε can always be transformed into a NFA, the properties are also true for NFAs.

Informal introduction

For example, lets suppose an NFA-ε contains two state 1 and 2 and it can move to state 2 without consuming any input symbols. If it is in state 1, with the next input symbol an a then there is an ambiguity: Is the system in state 1, or state 2, before consuming the letter a? Because of this ambiguity, it is more convenient to talk of the set of possible states the system may be in. Thus, before consuming letter a, the NFA-ε may be in any one of the states out of the set {1,2}. Equivalently, one may imagine that the NFA is in state 1 and 2 'at the same time' and this gives an informal hint of the powerset construction that translates an NFA to an equivalent DFA equivalent to an NFA.[citation needed]

Formal definition

A NFA-ε is represented formally by a 5-tuple, (Q, Σ,Δ, q0, F), consisting of

  • a finite set of states Q
  • a finite set of input symbols Σ
  • a transition relation Δ :Q × (Σ ∪{ε}) → P(Q)
  • an initial (or start) state q0 ∈ Q
  • a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q and ε denotes empty string. For a q ∈ Q, let E(q) denote the set of states that are reachable from state q by following ε-transitions in the transition relation Δ, i.e., p ∈ E(q) iff there is a sequence of states q1,...,qk such that q1=q, (qi, ε, qi+1) ∈ Δ for each 1 ≤ i < k, and qk = p. E(q) is known ε-closure of q. The ε-closure of a subset of states is also defined in the following way. For P ⊆ Q, let E(P) = ∪q ∈ P E(q).

Let w = a1a2 ... an be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of of states, r0,r1, ..., rn, exists in Q with the following conditions:

  1. r0 ∈ E(q0),
  2. r' ∈ Δ(ri, ai+1) and ri+1 ∈ E(r') for each i = 0, ..., n−1, and
  3. rn ∈ F.

In words, the first condition says that the machine starts at the state that is reachable from the start state q0 via ε-transitions. The second condition says that after reading ai, the machine takes a transition of Δ from ri to r', and then takes any number of ε-transitions according to Δ to move from r' to ri+1. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

It can be shown that ordinary NFA and NFA-ε are equivalent, in that, given either one, one can construct the other, which recognizes the same language.

For more comprehensive introduction of the formal definition see automata theory.

Example

The state diagram for M

Let M be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.

In formal notation, let M = ({s0, s1, s2, s3, s4}, {0, 1}, Δ, s0, {s1, s3}) where the transition relation Δ can be defined by this state transition table:

0
1
ε
S0
{}
{}
{S1, S3}
S1
{S2}
{S1}
{}
S2
{S1}
{S2}
{}
S3
{S3}
{S4}
{}
S4
{S4}
{S3}
{}

M can be viewed as the union of two DFAs: one with states {S1, S2} and the other with states {S3, S4}. The language of M can be described by the regular language given by this regular expression (1*(01*01*)*) ∪ (0*(10*10*)*). We define M using ε-moves but M can be defined without using ε-moves.

Equivalence to NFA and DFA

Let A = (Q, Σ,Δ, q0, F) be a NFA-ε. The NFA A' = (Q, Σ, Δ', E(q0), F) is equivalent to A, where for each a ∈ Σ and q ∈ Q, Δ'(q,a) = E( Δ(q,a) ). Subsequently, the NFA can be translated into DFA using powerset construction.

Closure properties

If NFA-εs recognize the languages that are obtained by applying an operation on the NFA-ε recognizable languages then NFA-εs are said to be closed under the operation. The NFA-εs are closed under the following operations.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Nondeterministic_finite_automaton_with_ε-moves&oldid=480470169"