Automatentheorie, ein Zweig der theoretischen Informatik, gründete seine Wurzeln im 20. ten Jahrhundert, als Mathematiker sowohl theoretisch begann mit der Entwicklung und buchstäblich Maschinen , die bestimmte Merkmale des Menschen imitiert, Abschluss Berechnungen schneller und zuverlässiger. Die Automatentheorie befasst sich mit der Logik der Berechnung in Bezug auf einfache Maschinen, die als Automaten bezeichnet werden .
Durch Automaten können Informatiker verstehen, wie Maschinen Funktionen berechnen und Probleme lösen und vor allem, was es bedeutet, eine Funktion als berechenbar zu definieren oder eine Frage als entscheidbar zu beschreiben .
Automaten sind abstrakte Modelle von Maschinen, die Berechnungen an einer Eingabe durchführen, indem sie sich durch eine Reihe von Zuständen oder Konfigurationen bewegen. Bei jedem Berechnungszustand bestimmt eine Übergangsfunktion die nächste Konfiguration auf der Grundlage eines endlichen Abschnitts der gegenwärtigen Konfiguration. Als Ergebnis akzeptiert die Berechnung, sobald sie eine akzeptierende Konfiguration erreicht, diese Eingabe. Finite Automaten können in zwei Typen eingeteilt werden:
- Deterministischer endlicher Automat (DFA)
- Nichtdeterministischer endlicher Automat (NDFA/NFA)
Contents
Was ist DFA (Deterministischer endlicher Automat)?
Ein deterministischer endlicher Automat (DFA), auch als deterministischer endlicher Akzeptor (DFA), deterministischer endlicher Automat (DFSM) oder deterministischer endlicher Automat (DFSA) bezeichnet, ist ein endlicher Automat, der eine gegebene Zeichenkette akzeptiert oder ablehnt. durch Durchlaufen einer durch die Zeichenfolge eindeutig bestimmten Zustandssequenz.
Es kann auch als abstraktes mathematisches Konzept beschrieben werden, das häufig in Hardware und Software zur Lösung verschiedener spezifischer Probleme implementiert wird. Ein DFA kann beispielsweise eine Software modellieren, die entscheidet, ob Online-Benutzereingaben wie E-Mail-Adressen gültig sind oder nicht.
DFAs recognize exactly the set of regular languages, which are, among other things, useful for doing lexical analysis and pattern matching. DFAs can be built from nondeterministic finite automata (NFAs) using the powerset construction method.
What You Need To Know About DFA
- Deterministic Finite Automata is a type FA whereby only one path is possible for any specific input to transit from its current state to the next state. There usually exists a unique transition for each input symbol.
- DFA is an abstract mathematical concept. It is used in software and hardware for finding solutions to specific problems.
- DFA can be understood as one machine and a DFA machine can be constructed for every input and output.
- DFAs are designed from nondeterministic finite automata (NFAs) by incorporating the powerset construction method.
- In DFA, the next possible state is distinctly set.
- Backtracking is allowed in DFA.
- DFA recognizes natural languages to perform lexical analysis, pattern matching etc.
- DFA cannot use empty string transition.
- DFA will produce a unique computation /run enabling the automaton of each input string.
- For every symbol of the alphabet, there is only one state transition in DFA.
- DFA reject the string in case the termination state is other than the accepting state.
- A DFA is best explained in the form of one machine and not as separate units for computing purposes.
- DFA is more difficult to construct.
- DFA requires more space.
- In DFA we cannot move from one state to another without consuming a symbol.
- The time needed for executing an input string is less when compared to NFA.
- In DFA transition function, the number of the next states is zero or one or more.
- All DFA are NFA.
What Is NFA(Nondeterministic Finite Automaton)?
A nondeterministic finite automaton (NFA) also referred to as nondeterministic finite-state machine, were introduced in 1959 by Michael O. Rabin and Dana Scott. Nondeterminism is an important concept in the theory of computing. It refers to the possibility of having multiple choices for what can happen at various points in a computation.
An NFA, similar to a DFA, consumes a string of input symbols. For each input symbol, it transitions to a new state until all input symbols have been consumed. In each step, the automaton arbitrarily chooses one of the applicable transitions. If there exist some sequence of choices leading to an accepting state after completely consuming the input, it is accepted. Otherwise, if no choice sequence at all can consume all the input and lead to an accepting state, the input is rejected.
What You Need To Know About NFA
- Non-Deterministic Finite Automata is a type of FA whereby it is possible to have many paths for a given set of inputs to make their transition from their current state to the next states.
- In NFA, the transitions are not uniquely determined by their input symbol or source state.
- NFA can be understood as several little machines that compute together and there is no possibility of constructing an NFA machine for every input and output.
- In NFA, each pair of state and input symbol can have many possible next states.
- In NFA, backtracking may or may not be allowed.
- The reading of input symbols is not required for every individual state transition.
- NFA can use empty string transition.
- No user-specifications are required for making NFAs react in line to symbols.
- NFA rejects the string only when all branches of the NFA are dead or do not accept the string.
- NFA is a collection of multiple little-sized units that are combined together to perform computation activities.
- NFA is easier to construct.
- NFA requires little space.
- NFA allows (null) as the second argument of the transition function. This means that the NFA can make a transition without consuming an input symbol.
- Time needed for executing an input string is more when compared to DFA.
- In NFA transition function, the number of next states is exactly one.
- Not all NFA are DFA.
Difference Between DFA And NFA In Tabular Form
| BASIS OF COMPARISON | DFA | NFA |
| Description | Deterministic Finite Automata is a type FA whereby only one path is possible for any specific input to transit from its current state to the next state. There usually exists a unique transition for each input symbol. | Non-Deterministic Finite Automata is a type of FA whereby it is possible to have many paths for a given set of inputs to make their transition from their current state to the next states. |
| Next Possible States | In DFA, the next possible state is distinctly set. | In NFA, each pair of state and input symbol can have many possible next states. |
| Backtracking | Backtracking is allowed in DFA. | In NFA, backtracking may or may not be allowed. |
| Reading Of Input Symbols | DFA recognizes natural languages to perform lexical analysis, pattern matching etc. | The reading of input symbols is not required for every individual state transition. |
| Empty String Transition | DFA cannot use empty string transition. | NFA can use empty string transition. |
| State Transition | For every symbol of the alphabet, there is only one state transition in DFA. | No user-specifications are required for making NFAs react in line to symbols. |
| String Rejection | DFA reject the string in case the termination state is other than the accepting state. | NFA rejects the string only when all branches of the NFA are dead or do not accept the string. |
| Description In Terms Of Units | A DFA is best explained in the form of one machine and not as separate units for computing purposes. | NFA is a collection of multiple little-sized units that are combined together to perform computation activities. |
| Construction | DFA is more difficult to construct. | NFA is easier to construct. |
| Space Requirement | DFA requires more space. | NFA requires little space. |
| Transition From One State To Another | In DFA we cannot move from one state to another without consuming a symbol. | NFA allows (null) as the second argument of the transition function. This means that the NFA can make a transition without consuming an input symbol. |
| Time Required For Executing An Input String | The time needed for executing an input string is less when compared to NFA. | Time needed for executing an input string is more when compared to DFA. |
| Number Of Next States | In DFA transition function, the number of the next states is zero or one or more. | In NFA transition function, the number of next states is exactly one. |
| Relation | All DFA are NFA. | Not all NFA are DFA. |
