المحاضرة الثالثة - احتسابية1

Finite state Automata , D. Finite state Automata , Nondeterministic FSA
Construct an Equivalent DFA from NFA.

FINITE AUTOMATA

A finite automaton is a collection of three things:
1. A finite set of states, one of which is designated as the initial state, called
the start state, and some (maybe none) of which are designated as final
states.
2. An alphabet ?of possible input letters, from which are formed strings,
that are to be read one letter at a time.
3. A finite set of transitions that tell for each state and for each letter of
the input alphabet which state to go to next.
The definition above is incomplete in the sense that it describes what a
finite automation is but not how it works. It works by being presented with
an input string of letters that it reads letter by letter starting at the leftmost
letter. Beginning at the start state the letters determine a sequence of states.
The sequence ends when the last input letter has been read.
Instead of writing out the whole phrase "finite automaton" it is customary
to refer to one by its initials, FA. The term FA is read by naming its letters, so
we say "an FA" even though it stands for "a finite automaton" and we say
"two FA s" even though it stands for "two finite automata".

Finite state Automata , D. Finite state Automata , Nondeterministic FSA
Construct an Equivalent DFA from NFA.

FINITE AUTOMATA

A finite automaton is a collection of three things:
1. A finite set of states, one of which is designated as the initial state, called
the start state, and some (maybe none) of which are designated as final
states.
2. An alphabet ?of possible input letters, from which are formed strings,
that are to be read one letter at a time.
3. A finite set of transitions that tell for each state and for each letter of
the input alphabet which state to go to next.
The definition above is incomplete in the sense that it describes what a
finite automation is but not how it works. It works by being presented with
an input string of letters that it reads letter by letter starting at the leftmost
letter. Beginning at the start state the letters determine a sequence of states.
The sequence ends when the last input letter has been read.
Instead of writing out the whole phrase "finite automaton" it is customary
to refer to one by its initials, FA. The term FA is read by naming its letters, so
we say "an FA" even though it stands for "a finite automaton" and we say
"two FA s" even though it stands for "two finite automata".