Recursive transition network (original) (raw)
Rekurzivní přechodová síť (RTN) je v teorii grafů schéma používané pro reprezentaci pravidel bezkontextových gramatik. Rekurzivní přechodové sítě se používají v programovací jazycích, při zpracování přirozeného jazyka a v lexikální analýze. Jakákoli věta, která je zkonstruovaná podle pravidel RTN se nazývá „dobře utvořená“. Strukturální prvky dobře utvořené věty mohou být také dobře utvořené věty nebo to mohou být jednodušší struktury. Z tohoto důvodu je RTN rekurzivní.
| Property | Value |
|---|---|
| dbo:abstract | Rekurzivní přechodová síť (RTN) je v teorii grafů schéma používané pro reprezentaci pravidel bezkontextových gramatik. Rekurzivní přechodové sítě se používají v programovací jazycích, při zpracování přirozeného jazyka a v lexikální analýze. Jakákoli věta, která je zkonstruovaná podle pravidel RTN se nazývá „dobře utvořená“. Strukturální prvky dobře utvořené věty mohou být také dobře utvořené věty nebo to mohou být jednodušší struktury. Z tohoto důvodu je RTN rekurzivní. (cs) A recursive transition network ("RTN") is a graph theoretical schematic used to represent the rules of a context-free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed according to the rules of an RTN is said to be "well-formed". The structural elements of a well-formed sentence may also be well-formed sentences by themselves, or they may be simpler structures. This is why RTNs are described as recursive. (en) Rekurencyjna sieć przejść (ang. recursive transition network, RTN) zwana czasem basic transition network (BTN) jest matematycznym modelem automatu do generowania/akceptowania słów gramatyki przedstawionym w postaci grupy skierowanych grafów. Na RTN składają się stany oraz łuki. Jest jeden stan początkowy i zbiór stanów końcowych. Łuki mogą być oznakowane symbolami terminalnymi, podobnie jak to jest w automacie skończonym, ale również symbolami nieterminalnymi z dodatkowymi akcjami PUSH I POP. Napotykając łuk z taką etykietą, zamiast przechodzić do następnego stanu, przechodzimy do początkowego stanu (operacja PUSH) innego lub tego samego grafu, gdzie kontynuujemy wędrówkę aż do któregoś ze stanów końcowych, gdzie wracamy (operacja POP) do grafu, w którym byliśmy poprzednio idąc do stanu, który wskazuje ten łuk. Łuki mogą mieć być któregoś z typu: WRD - symbol terminalnyCAT - przechodzimy, gdy symbol należy do pewnej kategorii (często używane w przetwarzaniu gramatyk języka naturalnego)JMP - przejście bez pobierania żadnego symbolu z wejścia, działa tak samo jak ε-przejścia automatu niedeterministycznegoPUSH - zapamiętane jest bieżące położenie (który graf i który stan) oraz przejście na początek odpowiedniego grafu.POP - to raczej nie typ łuku ale działanie, które następuje w stanach końcowych - przejście do miejsca, które zostało ostatnio odłożone na stos. Sieć RTN może sprawdzać gramatykę bezkontekstową, w odróżnieniu od automatów skończonych bez stosu ograniczonych do wyrażeń regularnych. Rozważmy gramatykę palindromiczną generowaną przez produkcje: * * * * Sieć RTN będzie wyglądała: (pl) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Fancy_noun_recursive_transition_network.svg?width=300 |
| dbo:wikiPageID | 7970632 (xsd:integer) |
| dbo:wikiPageLength | 1567 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 994148270 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Schematic dbr:Parsing dbr:Lexical_analysis dbc:Diagrams dbr:Context-free_grammar dbr:Computational_linguistics dbr:Formal_grammar dbr:Graph_theory dbr:Recursion dbc:Natural_language_processing dbr:Parse_tree dbr:Augmented_transition_network dbr:Sentence_(linguistics) dbr:Natural_language dbr:Programming_language dbr:Syntax_diagram dbr:Finite_state_machine dbr:Context_free_language dbr:File:Fancy_noun_recursive_transition_network.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Comp-ling-stub |
| dct:subject | dbc:Diagrams dbc:Natural_language_processing |
| rdf:type | yago:Artifact100021939 yago:Creation103129123 yago:Diagram103186399 yago:Drawing103234306 yago:Object100002684 yago:PhysicalEntity100001930 yago:Representation104076846 yago:Whole100003553 yago:WikicatDiagrams |
| rdfs:comment | Rekurzivní přechodová síť (RTN) je v teorii grafů schéma používané pro reprezentaci pravidel bezkontextových gramatik. Rekurzivní přechodové sítě se používají v programovací jazycích, při zpracování přirozeného jazyka a v lexikální analýze. Jakákoli věta, která je zkonstruovaná podle pravidel RTN se nazývá „dobře utvořená“. Strukturální prvky dobře utvořené věty mohou být také dobře utvořené věty nebo to mohou být jednodušší struktury. Z tohoto důvodu je RTN rekurzivní. (cs) A recursive transition network ("RTN") is a graph theoretical schematic used to represent the rules of a context-free grammar. RTNs have application to programming languages, natural language and lexical analysis. Any sentence that is constructed according to the rules of an RTN is said to be "well-formed". The structural elements of a well-formed sentence may also be well-formed sentences by themselves, or they may be simpler structures. This is why RTNs are described as recursive. (en) Rekurencyjna sieć przejść (ang. recursive transition network, RTN) zwana czasem basic transition network (BTN) jest matematycznym modelem automatu do generowania/akceptowania słów gramatyki przedstawionym w postaci grupy skierowanych grafów. Na RTN składają się stany oraz łuki. Jest jeden stan początkowy i zbiór stanów końcowych. Łuki mogą być oznakowane symbolami terminalnymi, podobnie jak to jest w automacie skończonym, ale również symbolami nieterminalnymi z dodatkowymi akcjami PUSH I POP. Łuki mogą mieć być któregoś z typu: Rozważmy gramatykę palindromiczną generowaną przez produkcje: (pl) |
| rdfs:label | Rekurzivní přechodová síť (cs) Recursive transition network (en) Rekurencyjna sieć przejść (pl) |
| owl:sameAs | freebase:Recursive transition network yago-res:Recursive transition network wikidata:Recursive transition network dbpedia-cs:Recursive transition network dbpedia-pl:Recursive transition network https://global.dbpedia.org/id/4tioo |
| prov:wasDerivedFrom | wikipedia-en:Recursive_transition_network?oldid=994148270&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Fancy_noun_recursive_transition_network.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Recursive_transition_network |
| is dbo:wikiPageDisambiguates of | dbr:RTN |
| is dbo:wikiPageWikiLink of | dbr:Flowchart dbr:Postmodernism_Generator dbr:RTN dbr:HFST dbr:Augmented_transition_network dbr:Filtered-popping_recursive_transition_network dbr:Outline_of_natural_language_processing dbr:Syntax_diagram |
| is foaf:primaryTopic of | wikipedia-en:Recursive_transition_network |
