[go: up one dir, main page]
Scribd
Upload
111 views11 pages

CSC312 Automata Theory: Chapter # 5 by Cohen

This document summarizes lecture 6 on finite automata from the course CSC312 Automata Theory. It defines a finite automaton as a model of computation consisting of a finite set of states, input alphabet, transitions between states based on input letters, an initial state, and final states. Examples are given to demonstrate finite automata diagrams and state transition tables that recognize specific regular expressions. Important notes are provided on constructing finite automata from regular expressions.

Uploaded by

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

CSC312 Automata Theory: Chapter # 5 by Cohen

This document summarizes lecture 6 on finite automata from the course CSC312 Automata Theory. It defines a finite automaton as a model of computation consisting of a finite set of states, input alphabet, transitions between states based on input letters, an initial state, and final states. Examples are given to demonstrate finite automata diagrams and state transition tables that recognize specific regular expressions. Important notes are provided on constructing finite automata from regular expressions.

Uploaded by

Faizan Rahim
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 11

CSC312

Automata Theory
Lecture # 6

Chapter # 5 by Cohen

Finite Automata
Automaton
An automaton is an abstract model of a
computer, which accepts some input (a
string), produces output (yes/no or a
string), and may have internal, storage
(usually, as stack or tape).
An automaton operates in a discrete
time frame (like a real computer). A
particular state of the automaton,
including the stat of the control unit,
input, and storage, is called a
configuration.
2
Finite Automaton
Finite automata are computing devices that
accept/recognize regular languages and are
used to model operations of many systems
we find in practice.
In the word ‘Finite Automata’, Finite means
the no. of letters in the input alphabet &
the no. of states are both finite and
automata means automatic.

3
Finite Automaton
(also called acceptor/recognizer)
A Finite Automaton (FA) is a collection of
three things
1.Finite set of input letter  from which
input strings are formed.
2.Finite number of states, having one initial
and some (maybe none) final states.
3.Finite set of transitions i.e. for each
state and for each input letter there is a
transition showing how to move from one
state to another.
4
Finite Automaton

Input
String

Output
Finite String
Automaton

5
Finite Accepter

Input
String
Output
“Accept”
Finite
or
Automaton
“Reject”

6
FA - Examples
Example:
Σ = {a,b}
States: x, y, z where x is an initial state and
z is final state.
Transitions:
At state x reading a, go to state z
At state x reading b, go to state y
At state y reading a, b go to state y
At state z reading a, b go to state z
7
Example:
State Transition Table
The FA is
Old New States
States (Transition Diagram)
Reading a Reading b
x- z y
y y y b
z+ z z

RE :
a(a+b)*
8
Example:
State Transition Table
The FA is
Old New States
(Transition Diagram)
States
Reading a Reading b
x y y
y x x

RE :
((a+b)(a+b))*

9
Example:
State Transition Table
Old New States
The FA is
States (Transition Diagram)
Reading a Reading b
x- y z
y x z
z+ z z
It accepts at least one b somewhere in the
strings
RE :
(a+b)*b(a+b)* or a*b(a+b)*
10
Important Notes
1. If  is present in the language we can make the
FA accept  by making the start state as the
final state.
2. From every state there will be as many outgoing
arrows  as there are letters in the alphabet.
3. If any RE contains (a+b)* in the beginning we
shall first construct the FA by discarding that
(a+b)*, the initially discarded (a+b)* will be taken
into account by missing arrows & there will be no
dead end state.
4. When all the words of the language (finite) are
accepted by the FA then all the missing edges
will go to dead end state.
11

You might also like