Scribd
Upload
126 views11 pages

Epsilon-NFA: Definition and Elimination

The document discusses ε-NFAs (non-deterministic finite automata with epsilon transitions), which allow instantaneous state transitions without reading an input symbol. Though ε-NFAs add convenience, they recognize the same formal languages as regular NFAs. The document also describes how to eliminate epsilon transitions from an ε-NFA by constructing an equivalent NFA without epsilon transitions.

Uploaded by

John Johnston
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
126 views11 pages

Epsilon-NFA: Definition and Elimination

The document discusses ε-NFAs (non-deterministic finite automata with epsilon transitions), which allow instantaneous state transitions without reading an input symbol. Though ε-NFAs add convenience, they recognize the same formal languages as regular NFAs. The document also describes how to eliminate epsilon transitions from an ε-NFA by constructing an equivalent NFA without epsilon transitions.

Uploaded by

John Johnston
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

NFA with epsilon

transitions
Sipser pages 47-54
NFAs with Transitions

We extend the class of NFAs by


allowing instantaneous () transitions:
1. The automaton may be allowed to change
its state without reading the input symbol.
2. In diagrams, such transitions are depicted
by labeling the appropriate arcs with .
3. Note that this does not mean that has
become an input symbol. On the
contrary, we assume that the symbol
does not belong to any alphabet.
example

{ an | n is even or divisible by 3 }
This is the version of
the NFA on page 53
of Sipser.
Definition

A -NFA is a quintuple A=(Q,,,q0,F) where

Q is a set of states
is the alphabet of input symbols
q0Q is the initial state
F Q is the set of final states
Q P(Q) is the transition function
Note is never a member of
is defined to be (
-NFA

-NFAs add a convenient feature but (in a sense)


they bring us nothing new: they do not extend
the class of languages that can be represented.
Both NFAs and -NFAs recognize exactly the
same languages.

-transitions are a convenient feature: try to


design an NFA for the even or divisible by 3
language that does not use them!
Hint, you need to use something like the product
construction from union-closure of DFAs
-Closure

-closure of a state
The -closure of the state q, denoted ECLOSE(q), is the set that
contains q, together with all states that can be reached starting
at q by following only -transitions.

In the above example:


ECLOSE(P) ={P,Q,R,S}
ECLOSE(R)={R,S}
ECLOSE(x)={x} for the remaining 5 states
{Q,Q1,R1,R2,R2}

Computing eclose
Compute eclose by adding new
states until no new states can be
added

Start with [P]


Add Q and R to get [P,Q,R]
Add S to get [P,Q,R S]
No new states can be added
Elimination of-Transitions

Given an -NFA N, this construction produces an


NFA N' such that L(N')=L(N).

The construction of N' begins with N as input,


and takes 3 steps:

1. Make p an accepting state of N' iff ECLOSE(p) contains


an accepting state of N.
2. Add an arc from p to q labeled a iff there is an arc
labeled a in N from some state in ECLOSE(p) to q.
3. Delete all arcs labeled .
Make p an
accepting state of
N' iff ECLOSE(p)
contains an
accepting state of
N.
Add an arc from p to q
labeled a iff there is
an arc labeled a in N
from some state in
ECLOSE(p) to q.

Delete all arcs


labeled .
Why does it work?

The language accepted by the


automaton is being preserved during
the three steps of the construction:
L(N)=L(N1)=L(N2)=L(N3)

Each step here requires a proof. A


Good exercise for you to do!

Theorem
Any NFAe can be turned into an NFA

How?

You might also like