PPT: Finite Automata

# PPT: Finite Automata - Theory of Computation - Computer Science Engineering (CSE)

 Download, print and study this document offline
``` Page 1

1
Finite Automata
Page 2

1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
Page 3

1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
Page 4

1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
4
What does a DFA do on
reading an input string?
n Input: a word w in ?*
n Question: Is w acceptable by the DFA?
n Steps:
n Start at the “start state” q
0
n For every input symbol in the sequence w do
n Compute the next state from the current state, given the
current input symbol in w and the transition function
n If after all symbols in w are consumed, the current
state is one of the accepting states (F) then accept
w;
n Otherwise, reject w.
Page 5

1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
4
What does a DFA do on
reading an input string?
n Input: a word w in ?*
n Question: Is w acceptable by the DFA?
n Steps:
n Start at the “start state” q
0
n For every input symbol in the sequence w do
n Compute the next state from the current state, given the
current input symbol in w and the transition function
n If after all symbols in w are consumed, the current
state is one of the accepting states (F) then accept
w;
n Otherwise, reject w.
5
Regular Languages
n Let L(A) be a language recognized by a
DFA A.
n Then L(A) is called a “Regular Language”.
n Locate regular languages in the
Chomsky Hierarchy
```

## Theory of Computation

18 videos|56 docs|44 tests

## FAQs on PPT: Finite Automata - Theory of Computation - Computer Science Engineering (CSE)

 1. What is a finite automaton in computer science engineering?
Ans. A finite automaton, also known as a finite state machine, is a mathematical model used in computer science engineering to represent and analyze systems that can be in a finite number of states at any given time. It consists of a set of states, a set of input symbols, a transition function, and an initial state.
 2. How does a finite automaton work in computer science engineering?
Ans. A finite automaton works by transitioning between different states based on the input it receives. It starts in an initial state and reads input symbols one at a time. The transition function defines the next state based on the current state and the input symbol. This process continues until the automaton reaches a final state or the input symbols are exhausted.
 3. What is the significance of finite automata in computer science engineering?
Ans. Finite automata are significant in computer science engineering as they provide a formal and systematic approach to model and analyze various systems. They are used in areas such as compiler design, natural language processing, pattern recognition, and protocol design. Understanding finite automata helps in solving complex problems efficiently.
 4. What are the types of finite automata?
Ans. There are two main types of finite automata: deterministic finite automata (DFA) and nondeterministic finite automata (NFA). DFA has a unique transition for each input symbol, while NFA can have multiple transitions for a single input symbol or even epsilon transitions, where no input symbol is consumed.
 5. How to convert a nondeterministic finite automaton (NFA) to a deterministic finite automaton (DFA)?
Ans. NFA to DFA conversion is done using the subset construction method. In this method, each state of the DFA corresponds to a set of states in the NFA. Initially, the DFA has only the start state, and then the transitions are determined based on the NFA transitions. The final states of the DFA are the sets of NFA states that contain at least one final state. This conversion allows for efficient implementation and analysis of the automaton.

## Theory of Computation

18 videos|56 docs|44 tests

### Up next

 Explore Courses for Computer Science Engineering (CSE) exam

### Top Courses for Computer Science Engineering (CSE)

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;