Discrete Mathematics

298

mSCRETEMATHEMATICS--------------------------------------------------

Example 4 Here is a nondeterministic automaton withE-transitions accepting the set

{x

E {a}*

II

xI

is

divisible by 3

or

5}:

The automaton chooses at the outset which

of

the two conditions to check for (divisibility by 3

or

5)

and slides to one

of

the two loops accordingly without reading an input symbol.

The main benefit

of

E -transitions is convenience. They do not really add any power: a modified subset

construction involving the notion

of

E -closure can

be

used

to

show that every

NF

A with E -transitions can

be

simulated

by

a

DFA

without E -transitions, thus all sets ...