Nondeterministic Finite Automata and the NFA to DFA Algorithm
Explore the concepts of nondeterministic finite automata, epsilon transitions, and the NFA to DFA algorithm. Learn about the differences between DFA and NFA, as well as how to convert NFAs to DFAs. Discover how two FAs can be equivalent and delve into examples to solidify your understanding.
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
Finite Automata Finite Automata Part Two : Nondeterministic Finite Automata Part Two : Nondeterministic Finite Automata
Example 1 Example 1 accept all strings of 0 and 1 ending in 11 0 1 1 A B C 1 Given the word "1111", for the first '1' do we stay in state A or go to state B? A machine cannot determine that. A string is accepted by an NFA if there is any sequence of transitions that ends in a favorable state.
DFA v. NFA DFA v. NFA Both: one start state one or more accepting states DFA: every state indicates how to process each character of the input alphabet in exactly one way NFA: states may have more than one possible transition for an input just try them all states may not indicate how to process a particular input indicates the word is not accepted
Example 2 Example 2 - - Epsilon Transitions Epsilon Transitions - change state without consuming an input character This NFA accepts words of 0 and 1 that contain either 11 or 101. 1 1 A B C 0 0,1 0,1 1 D E Example words: 0 0 0 0 -> A A A A - rejected 0 1 1 0 -> A B C e E - accepted 1 0 0 1 -> several possible transitions, none reach a favorable state
FA Theory Two FAs are equivalent if they accept the same language. For each NFA, there is an equivalent DFA. We will skip the boring proof.
NFA to DFA algorithm 1. Start the DFA with the start state of the NFA. 2. For each new state in the DFA for each character in the alphabet if there is more than one choice of transitions, create a new state that is the union of those two states if that character does not lead out of this state, create transition to a new dead state 3. Favorable states are any states that reference a favorable state from the NFA.
NFA to DFA Example 1 Again, accept all words of 0 and 1 that end with 11. NFA in table format: 0 1 > A {A} {A,B} B {C} C 0 1 1 A B C 1 new DFA - step one 0 1 > A A AB new DFA - step two 0 1 > A A AB AB A ABC Final DFA > A A AB AB A ABC ABC A ABC 0 1 state A is already defined state AB is new state AB is the union of states A and B 0: {A} U = A 1: {A,B} U {C} = ABC
NFA to DFA Example 1 continued Accept all words of 0 and 1 that end with 11. Final DFA > A A AB AB A ABC ABC A ABC 0 0 1 1 1 A B C 1 1 0 1 1 A AB ABC 0 0
NFA to DFA example 2 accept all binary words that start with zero NFA in Table Format: 0 1 >A B B B B 0 0,1 A B new DFA: 0 1 >A B C B B B C C C 0 0,1 A B 1 0,1 C C is a trap state.
Practice Practice 1. Draw an NFA that accepts strings of {0,1} that contain "11". 2. Convert that NFA to a DFA.
Epsilon NFA to DFA example Epsilon NFA to DFA example Again, this NFA accepts words of 0 and 1 that contain either 11 or 101. 1 1 A B C 0 0,1 0,1 1 D E e-NFA: 0 1 e* >A A A,B A B D C B C - - C,E D - E D E E E E states reachable by using zero or more epsilon moves These cells are pointers to the correct row. Use the e* values from those rows.
e e- -NFA NFA to DFA to DFA example example continued continued e-NFA: DFA: 0 1 e* >A A A,B A B D C B C - - C,E D - E D E E E E 0 1 >A A AB AB AD ABCE AD A ABE ABCE ADE ABCE ADE AE ABE ABE ADE ABE AE AE ABE
0 1 >A A AB AB AD ABCE AD A ABE ABCE ADE ABCE ADE AE ABE ABE ADE ABE AE AE ABE e e- -NFA to DFA NFA to DFA continued continued accept words of 0 and 1 that contain either 11 or 101 0 1 0 1 0 A AB AD ABE 1 1 1 0 1 0 ABCE ADE AE 0 0 1
Practice Practice The following eNFA accepts strings of {a,b} that start with a single 'a', followed by zero or more 'b's, and ending with a single 'a'. ab*a b b a e B a D D A C a
