This HTML5 document contains 228 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-elhttp://el.dbpedia.org/resource/
dbpedia-nohttp://no.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-hrhttp://hr.dbpedia.org/resource/
n7http://fr.dbpedia.org/resource/Modèle:
dbpedia-arhttp://ar.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n23http://g.co/kg/m/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n8http://fr.dbpedia.org/resource/Fichier:
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
n28http://ma-graph.org/entity/
prop-frhttp://fr.dbpedia.org/property/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n33http://www-igm.univ-mlv.fr/~perrin/Recherche/Publications/Loi/
n27https://commons.wikimedia.org/wiki/Category:
dbpedia-ithttp://it.dbpedia.org/resource/
n38http://smc.sourceforge.net/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
n22http://bs.dbpedia.org/resource/
wikipedia-frhttp://fr.wikipedia.org/wiki/
dbpedia-zhhttp://zh.dbpedia.org/resource/
n13https://github.com/bnogent/
n17http://sakharov.net/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbpedia-fr:Automate_fini_non_déterministe
rdfs:label
Automate fini non déterministe Autómata finito no determinista Недетерминированный конечный автомат Máquina de estados finitos não determinística Недетермінований скінченний автомат
rdfs:comment
Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte.
rdfs:seeAlso
n27:Finite_state_machine
owl:sameAs
dbpedia-fa:اتوماتون_تعیین‌ناپذیر_متناهی dbpedia-hr:Nedeterministički_konačni_automat dbpedia-he:אוטומט_סופי_לא_דטרמיניסטי dbpedia-uk:Недетермінований_скінченний_автомат dbpedia-ru:Недетерминированный_конечный_автомат dbpedia-ca:Autòmat_finit_no_determinista dbpedia-el:Μη_ντετερμινιστικό_πεπερασμένο_αυτόματο n22:Nedeterministički_konačni_automat n23:02_w6j dbpedia-sr:Недетерминистички_коначни_аутомат n28:158008952 dbpedia-hu:Nemdeterminisztikus_véges_állapotú_gép dbpedia-ja:非決定性有限オートマトン dbpedia-pt:Máquina_de_estados_finitos_não_determinística dbpedia-zh:非确定有限状态自动机 dbpedia-it:Automa_a_stati_finiti_non_deterministico dbpedia-pl:Niedeterministyczny_automat_skończony dbpedia-ko:비결정적_유한_상태_기계 dbpedia-ar:آلة_محدودة_الحالات_غير_قطعية dbpedia-sh:Nedeterministički_konačni_automat wikidata:Q617295 dbpedia-tr:Deterministik_olmayan_sonlu_durum_makinesi dbpedia-es:Autómata_finito_no_determinista dbpedia-no:Ikke-deterministisk_endelig_tilstandsmaskin dbpedia-de:Nichtdeterministischer_endlicher_Automat dbr:Nondeterministic_finite_automaton
dbo:wikiPageID
1571839
dbo:wikiPageRevisionID
191426999
dbo:wikiPageWikiLink
dbpedia-fr:Vérification_de_modèles dbpedia-fr:Matrice_creuse dbpedia-fr:Lemme_d'Arden dbpedia-fr:Théorie_des_automates n8:Automate-impair.png dbpedia-fr:Construction_de_Glushkov n8:Automate-asynchrone.png dbpedia-fr:Langage_formel n8:Automate-de-Thompson.png n8:AutomatePourProduit.png dbpedia-fr:Machine_de_Turing n8:AutomatePourUnion.png dbpedia-fr:Grammaire_non_contextuelle n8:AutomatePourEtoile.png category-fr:Méthode_formelle dbpedia-fr:Grep dbpedia-fr:Langage_rationnel dbpedia-fr:Janusz_A._Brzozowski dbpedia-fr:Hiérarchie_de_Chomsky dbpedia-fr:Machine_abstraite dbpedia-fr:Matrice_(mathématiques) dbpedia-fr:Linguistique n8:DFA_example_multiplies_of_3.png dbpedia-fr:Compilateur dbpedia-fr:Machine_de_Moore dbpedia-fr:Machine_de_Mealy dbpedia-fr:Monoïde dbpedia-fr:Algorithme_de_recherche_de_sous-chaîne dbpedia-fr:Monoïde_syntaxique dbpedia-fr:Epsilon_transition dbpedia-fr:Switch_(instruction) dbpedia-fr:Circuit_intégré dbpedia-fr:Unix category-fr:Calculabilité dbpedia-fr:Arbre_enraciné dbpedia-fr:Algorithme_de_Thompson dbpedia-fr:Expression_régulière dbpedia-fr:Ken_Thompson dbpedia-fr:Produit_cartésien dbpedia-fr:Action_de_groupe_(mathématiques) dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Suite_de_Prouhet-Thue-Morse dbpedia-fr:Transducteur_fini dbpedia-fr:Mathématiques_discrètes dbpedia-fr:Inclusion_(mathématiques) dbpedia-fr:Automate_pondéré dbpedia-fr:Automate_sur_les_mots_infinis dbpedia-fr:Minimisation_d'un_automate_fini_déterministe dbpedia-fr:Structure_de_Kripke dbpedia-fr:Automate_de_Muller dbpedia-fr:Automate_fini_inambigu dbpedia-fr:Système_de_transition_d'états dbpedia-fr:Automate_fini_déterministe dbpedia-fr:Informatique dbpedia-fr:Automate_transposé dbpedia-fr:Automate_à_pile dbpedia-fr:Bit n8:Automate-synchronise.png dbpedia-fr:Viktor_Glouchkov n8:Automate_reconnaissant_les_mots_commencant_par_ab.png n8:Automate_déterminisé.png dbpedia-fr:Mot_(mathématiques) n8:Automate_reconnaissant_les_mots_finissant_par_ab.png dbpedia-fr:Automate_de_Rabin n8:AutomatePourVideMotVideLettre.png category-fr:Théorie_des_automates n8:Automate_déteminisé_émondé.png dbpedia-fr:Théorie_des_graphes dbpedia-fr:Logique_programmable dbpedia-fr:Algorithme_de_Conway dbpedia-fr:Automate_de_Büchi category-fr:Automates_finis_et_langages_réguliers dbpedia-fr:Automate_d'arbres dbpedia-fr:Construction_par_sous-ensembles dbpedia-fr:Mot dbpedia-fr:Stephen_Cole_Kleene dbpedia-fr:Alphabet
dbo:wikiPageExternalLink
n13:state-machine n17:fsm.html n33:copie3.ps n38:
dbo:wikiPageLength
46400
dct:subject
category-fr:Calculabilité category-fr:Méthode_formelle category-fr:Théorie_des_automates category-fr:Automates_finis_et_langages_réguliers
prop-fr:wikiPageUsesTemplate
n7:Théorème n7:Indente n7:Introduction_to_Automata_Theory,_Languages,_and_Computation n7:Langages_formels,_calculabilité_et_complexité n7:Lien n7:2autres n7:Commentaire_biblio n7:' n7:, n7:ISBN n7:Loupe n7:Palette n7:Palette_Automates_finis_et_langages_réguliers n7:Ouvrage n7:P. n7:N° n7:Autres_projets n7:Article_détaillé n7:Article n7:Références n7:Portail
prov:wasDerivedFrom
wikipedia-fr:Automate_fini_non_déterministe?oldid=191426999&ns=0
foaf:depiction
n10:DFA_example_multiplies_of_3.png n10:Automate_reconnaissant_les_mots_commencant_par_ab.png n10:Automate_reconnaissant_les_mots_finissant_par_ab.png n10:Automate_déteminisé_émondé.png n10:Automate_déterminisé.png n10:AutomatePourEtoile.png n10:AutomatePourProduit.png n10:AutomatePourUnion.png n10:AutomatePourVideMotVideLettre.png n10:Automate-asynchrone.png n10:Automate-de-Thompson.png n10:Automate-impair.png n10:Automate-synchronise.png
prop-fr:année
1964 1960 1961 2003 2015 2009 1999 1968
prop-fr:auteur
H. Yamada dbpedia-fr:Janusz_A._Brzozowski Werner Kuich dbpedia-fr:Ken_Thompson Heiko Vogler Manfred Droste Robert McNaughton Jacques Sakarovitch dbpedia-fr:Viktor_Glouchkov
prop-fr:commons
category:finite state machine
prop-fr:commonsTitre
Automate fini
prop-fr:doi
10.1109 10.1142
prop-fr:fr
table logique programmable
prop-fr:id
Brzozowski1964 DrosteEtAl2009 Sakarovitch Thompson1968 Glushkov1961
prop-fr:isbn
978 3642014917
prop-fr:journal
Comm. Assoc. Comput. Mach., vol. 11 Russian Math. Surveys, vol. 16 J. Assoc. Comput. Mach., vol. 11
prop-fr:lang
en
prop-fr:mois
janvier décembre
prop-fr:nom
Séébold Holzer Gruber
prop-fr:numéro
1 8
prop-fr:pages
1009 198 419 481 1 39
prop-fr:pagesTotales
816 608 198
prop-fr:prénom
Patrice Hermann Markus
prop-fr:périodique
IRE Trans. Electronic Computers Int. J. Found. Comput. Sci.
prop-fr:sousTitre
Méthodes et exercices corrigés
prop-fr:titre
Théorie des automates Derivatives of regular expressions Handbook of Weighted Automata Éléments de théorie des automates Regular expressions and state graphs for automata Regular expression search algorithm From Finite Automata to Regular Expressions and Back : A Summary on Descriptional Complexity The abstract theory of automata
prop-fr:trad
Programmable Logic Array
prop-fr:volume
26 EC-9
prop-fr:wiktionary
automate
prop-fr:éditeur
Springer-Verlag Vuibert
dbo:thumbnail
n10:DFA_example_multiplies_of_3.png?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Automate_fini_non_déterministe
dbo:abstract
Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. On distingue les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automaton ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non. Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing. Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-dessus, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est : . L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle.Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final). Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaquelettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 :