Generalized nondeterministic finite automaton (original) (raw)
In the theory of computation, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A GNFA must have only one start state and one accept state, and these cannot be the same state, whereas an NFA or DFA both may have several accept states, and the start state can be an accept state. A GNFA must have only one transition betwe
| Property | Value |
|---|---|
| dbo:abstract | In the theory of computation, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A GNFA must have only one start state and one accept state, and these cannot be the same state, whereas an NFA or DFA both may have several accept states, and the start state can be an accept state. A GNFA must have only one transition between any two states, whereas a NFA or DFA both allow for numerous transitions between states. In a GNFA, a state has a single transition to every state in the machine, although often it is a convention to ignore the transitions that are labelled with the empty set when drawing generalized nondeterministic finite state machines. (en) Na Teoria da computação, um autômato finito não determinístico generalizado (AFNG), também conhecido como autômato de expressãoou máquina de estados finita não determinística generalizada é uma variação doAFN onde cada transição é rotulada por alguma expressão regular. O AFNG lê blocos de símbolos da entrada, os quais constituem uma cadeia definida pela expressão regular associada à transição. Existem diversas diferenças entre uma máquina de estados finita usual e uma máquina de estados finita não determinística generalizada. Um AFNG deve possuir apenas um estado inicial e um estado de aceitação, e estes não podem ser o mesmo estado, enquanto que AFNs ou AFDs podem ambos ter vários estados de aceitação, e o estado inicial pode ser de aceitação. Um AFNG deve possuir apenas uma transição entre quaisquer dois estados, enquanto que AFNs ou AFDs permitem ambos muitas transições entre estados. Em um AFNG, um estado possui uma única transição para cada um dos outros estados da máquina, embora frequentemente seja uma convenção ignorar as transições que são rotuladas com o conjunto vazio no desenho de máquinas de estados finitas não determinísticas generalizadas. (pt) |
| dbo:wikiPageExternalLink | http://www.cs.sunysb.edu/~cse350/slides/rgExp2.pdf |
| dbo:wikiPageID | 653415 (xsd:integer) |
| dbo:wikiPageLength | 3364 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121857001 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Powerset_construction dbr:Nondeterministic_finite_automaton dbr:Deterministic_finite_automaton dbr:Regular_expression dbr:Derick_Wood dbr:Function_(mathematics) dbr:Conference_on_Implementation_and_Application_of_Automata dbr:Theory_of_computation dbc:Finite_automata dbr:Finite_set dbr:Formal_language dbr:LNCS dbr:Michael_Sipser dbr:N-tuple |
| dbp:wikiPageUsesTemplate | dbt:Doi |
| dct:subject | dbc:Finite_automata |
| gold:hypernym | dbr:Variation |
| rdf:type | dbo:Food |
| rdfs:comment | In the theory of computation, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression. The GNFA reads blocks of symbols from the input which constitute a string as defined by the regular expression on the transition. There are several differences between a standard finite state machine and a generalized nondeterministic finite state machine. A GNFA must have only one start state and one accept state, and these cannot be the same state, whereas an NFA or DFA both may have several accept states, and the start state can be an accept state. A GNFA must have only one transition betwe (en) Na Teoria da computação, um autômato finito não determinístico generalizado (AFNG), também conhecido como autômato de expressãoou máquina de estados finita não determinística generalizada é uma variação doAFN onde cada transição é rotulada por alguma expressão regular. O AFNG lê blocos de símbolos da entrada, os quais constituem uma cadeia definida pela expressão regular associada à transição. Existem diversas diferenças entre uma máquina de estados finita usual e uma máquina de estados finita não determinística generalizada. Um AFNG deve possuir apenas um estado inicial e um estado de aceitação, e estes não podem ser o mesmo estado, enquanto que AFNs ou AFDs podem ambos ter vários estados de aceitação, e o estado inicial pode ser de aceitação. Um AFNG deve possuir apenas uma transição ent (pt) |
| rdfs:label | Generalized nondeterministic finite automaton (en) Autômato finito não determinístico generalizado (pt) |
| owl:sameAs | freebase:Generalized nondeterministic finite automaton yago-res:Generalized nondeterministic finite automaton wikidata:Generalized nondeterministic finite automaton http://bs.dbpedia.org/resource/Generalizirani_nedeterministički_konačni_automat dbpedia-fa:Generalized nondeterministic finite automaton dbpedia-hr:Generalized nondeterministic finite automaton dbpedia-pt:Generalized nondeterministic finite automaton https://global.dbpedia.org/id/4kRGx |
| prov:wasDerivedFrom | wikipedia-en:Generalized_nondeterministic_finite_automaton?oldid=1121857001&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Generalized_nondeterministic_finite_automaton |
| is dbo:wikiPageRedirects of | dbr:GNFA dbr:Generalized_nondeterministic_finite-state_machine dbr:Generalized_nondeterministic_finite_automata dbr:Generalized_nondeterministic_finite_state_machine |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:State_diagram dbr:Finite-state_machine dbr:GNFA dbr:Generalized_nondeterministic_finite-state_machine dbr:Generalized_nondeterministic_finite_automata dbr:Generalized_nondeterministic_finite_state_machine |
| is foaf:primaryTopic of | wikipedia-en:Generalized_nondeterministic_finite_automaton |