Document Type
Open Educational Resource (OER)
Publication Date
11-2018
Recommended Citation
    Baldwin, Doug; Jasinski, James; Klein, Matt; McAlevey, Jack; Parks, Ian; Rohe, Susanna; Wakwella, Praveen; Wilson, John; and Wojick, Kevin, "Nondeterministic Finite Automata Correspond to Deterministic Ones" (2018). Computability OER.  1.
    
    
    
        https://knightscholar.geneseo.edu/computability-oer/1
    
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 License.
        nfa2dfa.zip (31 kB) 
    
 
	
	
	
    
    
    
	
		
		
		
	
	
	
	
	
	
	
	
	
	
	
COinS
 
				 
					 
					
				
			
Comments
An important and initially surprising result about finite automata is that every nondeterministic finite automaton is equivalent to a deterministic one, i.e., nondeterminism doesn't add any computational power to the basic model. Maheshwari and Smid give the construction that shows how to create a deterministic finite automaton from a nondeterministic one, but don't include a proof that this construction is correct. This resource provides that correctness proof.