NFA and DFA in Compiler Design - Explained with Examples
Learn about Non-Deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA) in compiler design. Understand their definitions, differences, and conversion process with detailed examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COMPILER DESIGN COMPILER DESIGN BCA 5thSemester 2020 Topic: NFA and DFA Topic: NFA and DFA Sakhi Bandyopadhyay Department of Computer Science and BCA Kharagpur College
Non Non- -Deterministic Finite Automata (NFA) Deterministic Finite Automata (NFA) Non-Deterministic Finite Automata is defined by the quintuple- M = (Q, , , q0, F) where- Q = finite set of states = non-empty finite set of symbols called as input alphabets : Q x 2Q is a total function called as transition function q0 Q is the initial state F Q is a set of final states
Non Non- -Deterministic Finite Automata (NFA) (Cont.) Deterministic Finite Automata (NFA) (Cont.) Example Q = finite set of states = {A, B, C, D, E, F} = input alphabets = {a, b, c} : Q x 2Qis the transition function q0 Q = the initial state = A F Q is a set of final states = {D, F}
Deterministic Finite Automata (NFA) Deterministic Finite Automata (NFA) A DFA is a collection of 5-tuples same as we described in the definition of FA. M = (Q, , , q0, F) Q: finite set of states : finite set of the input symbol q0: initial state F: final state : Transition function : Q x Q
Deterministic Finite Automata (NFA) Deterministic Finite Automata (NFA) Example Q: finite set of states = {q0, q1, q2} : finite set of the input symbol = {0, 1} q0: initial state = {q0} F: final state = {q2} : Transition function : Q x Q 1 Present State 0 q0 q0 q1 q1 q2 q1 *q2 q2 q2
Example 1 NFA to DFA Conversion NFA DFA State / Alphabet a b State / Alphabet a b q0 q0 q0, q1 q0 q0 {q0, q1} q1 *q2 {q0, q1} q0 *{q0, q1, q2} *q2 *{q0, q1, q2} q0 *{q0, q1, q2}
Example 2 NFA to DFA conversion NFA DFA State / Alphabet 0 1 State / Alphabet 0 1 q0 q0 q1, *q2 q0 q0 *{q1, q2} q1 q1, *q2 *q2 *{q1, q2} *{q0, q1, q2} *{q1, q2} *q2 q0, q1 q1 *{q0, q1, q2} *{q0, q1, q2} *{q1, q2}
