L11,L12 Finite State Automata

Finite Automata (FA)
A finite automata is a collection of three things:
1. A finite set of states, one of which is designed as the initial state,
called the start state, and some (may be none) of which are
designed 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.
Example if ?={a,b}, states={x,y,z}
Rules of transition:
1. From state x and input a go to state y.
2. From state x and input b go to state z.
3. From state y and input a go to state x.
4. From state y and input b go to state z.
5. From state z and any input stay at the state z.
Let x be the start state and z be the final state.
The FA above will accept all strings that have the letter b in them
and no other strings. The language associated with(or accepted by) this
Finite Automata (FA)
A finite automata is a collection of three things:
1. A finite set of states, one of which is designed as the initial state,
called the start state, and some (may be none) of which are
designed 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.
Example if ?={a,b}, states={x,y,z}
Rules of transition:
1. From state x and input a go to state y.
2. From state x and input b go to state z.
3. From state y and input a go to state x.
4. From state y and input b go to state z.
5. From state z and any input stay at the state z.
Let x be the start state and z be the final state.
The FA above will accept all strings that have the letter b in them
and no other strings. The language associated with(or accepted by) this
FA is the one defined by the regular expression: a*b(a+b)*
The set of all strings that do leave us in a final state is called the
language defined by the FA. The word abb is accepted by this FA, but
The word aaa is not.

The FA above will accept all strings that have the letter b in them
and no other strings. The language associated with(or accepted by) this
FA is the one defined by the regular expression: a*b(a+b)*
The set of all strings that do leave us in a final state is called the
language defined by the FA. The word abb is accepted by this FA, but
The word aaa is not.