NFA to DFA conversion: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== Problem Description== DFA refers to Deterministic Finite Automaton. A Finite Automata(FA) is said to be deterministic, if corresponding to an input symbol, there is single resultant state i.e. there is only one transition. NFA refers to Nondeterministic Finite Automaton. A Finite Automata(FA) is said to be non deterministic, if there is more than one possible transition from one state on the same input symbol. == Bounds Chart == File:NFA_to_DFA_conversionBoundsC...")
 
No edit summary
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:NFA to DFA conversion (NFA to DFA conversion)}}
DFA refers to Deterministic Finite Automaton. A Finite Automata(FA) is said to be deterministic, if corresponding to an input symbol, there is single resultant state i.e. there is only one transition.
== Description ==  


NFA refers to Nondeterministic Finite Automaton. A Finite Automata(FA) is said to be non deterministic, if there is more than one possible transition from one state on the same input symbol.  
Convert a given nondeterministic finite automota (NFA) to a deterministic finite automota (DFA).


== Bounds Chart ==
== Parameters ==  
[[File:NFA_to_DFA_conversionBoundsChart.png|1050px]]


== Step Chart ==
<pre>n: number of states in the given NFA</pre>
[[File:NFA_to_DFA_conversionStepChart.png|1050px]]
 
== Table of Algorithms ==  
 
{| class="wikitable sortable"  style="text-align:center;" width="100%"
 
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference


== Improvement Table ==
{| class="wikitable" style="text-align:center;" width="100%"
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
|-
| rowspan="1" | Exp/Factorial
| [https://ieeexplore.ieee.org/document/5392601 Rabin–Scott powerset construction (1959)]
|
|-
|-
| rowspan="1" | Polynomial > 3
 
|
| [[Rabin–Scott powerset construction ( NFA to DFA conversion)|Rabin–Scott powerset construction]] || 1959 || $O({2}^n)$ || $O({1})$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/5392601 Time]
|
|-
|-
| rowspan="1" | Cubic
|}
|
 
|
== Time Complexity graph ==
|-
 
| rowspan="1" | Quadratic
[[File:NFA to DFA conversion - Time.png|1000px]]
|
 
|
== Space Complexity graph ==
|-
 
| rowspan="1" | nlogn
[[File:NFA to DFA conversion - Space.png|1000px]]
|
 
|
== Pareto Decades graph ==
|-
 
| rowspan="1" | Linear
[[File:NFA to DFA conversion - Pareto Frontier.png|1000px]]
|
|
|-
| rowspan="1" | logn
|
|
|-|}

Revision as of 11:20, 15 February 2023

Description

Convert a given nondeterministic finite automota (NFA) to a deterministic finite automota (DFA).

Parameters

n: number of states in the given NFA

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Rabin–Scott powerset construction 1959 $O({2}^n)$ $O({1})$ Exact Deterministic Time

Time Complexity graph

NFA to DFA conversion - Time.png

Space Complexity graph

NFA to DFA conversion - Space.png

Pareto Decades graph

NFA to DFA conversion - Pareto Frontier.png

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=NFA_to_DFA_conversion&oldid=43962"