About: Nondeterministic finite automaton     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, is a finite-state machine that does not need to obey the restrictions set by DFA, where each of the transition is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

AttributesValues
rdfs:label
  • Nondeterministic finite automaton (en)
rdfs:comment
  • A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, is a finite-state machine that does not need to obey the restrictions set by DFA, where each of the transition is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. (en)
sameAs
dbp:wikiPageUsesTemplate
Subject
prov:wasDerivedFrom
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
Link from a Wikipage to another Wikipage
has abstract
  • A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, is a finite-state machine that does not need to obey the restrictions set by DFA, where each of the transition is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton). NFAs have been generalized in multiple ways, e.g., , finite-state transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata.Besides the DFAs, other known special cases of NFAsare unambiguous finite automata (UFA)and self-verifying finite automata (SVFA). (en)
foaf:isPrimaryTopicOf
is Wikipage redirect of
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git151 as of Feb 20 2025


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 925 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software