Automata theory (original) (raw)
نظرية التشغيل الذاتي أو نظرية الآلات ذاتية التشغيل أو نظرية الآلات المجرّدة (بالإنجليزية: Automata Theory) هي نظرية تهتم بتعريف ودراسة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحاسوبيّة في وقتنا الحالي، وتستخدم بكثرة كأداة للبرهان الرياضي الحاسوبي، لذلك فهي تعتبر من أهمّ ركائز علوم الحاسوب النظرية .
| Property | Value |
|---|---|
| dbo:abstract | La teoria d'autòmats és una branca de les ciències de la computació que estudia les màquines abstractes i els problemes que aquestes són capaços de resoldre. Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, compilador és, disseny de maquinari i intel·ligència artificial. La teoria d'autòmats està estretament relacionada amb la teoria del llenguatge formal, ja que els autòmats són classificats sovint per la classe de llenguatges formals que són capaços de reconèixer. Un autòmat és un model matemàtic per a una màquina d'estat finita (FSM les seves sigles en anglès). Una FSM és una màquina que, donada una entrada de símbols, "salta" a través d'una sèrie d'estats d'acord amb una funció de transició (que pot ser expressada com una taula). En la varietat comuna "Mealy" de FSMs, aquesta funció de transició diu a l'autòmat a quin estat canviar donats uns determinats estat i símbol. L'entrada és llegida símbol per símbol, fins que és "consumida" completament (pensi en aquesta com una cinta amb una paraula escrita en ella, que és llegida per un cap lectora de l'autòmat; el cap es mou al llarg de la cinta, llegint un símbol alhora) una vegada l'entrada s'ha esgotat, l'autòmat s'atura. Depenent de l'estat en què l'autòmat finalitza es diu que aquest ha acceptat o rebutjat l'entrada. Si aquest acaba en l'estat "accepta", l'autòmat accepta la paraula. Si ho fa en l'estat "rebutja", l'autòmat va rebutjar la paraula, el conjunt de totes les paraules acceptades per l'autòmat constitueixen el llenguatge acceptat pel mateix. (ca) La teoria d'autòmats és una branca de les ciències de la computació que estudia les màquines abstractes i els problemes que aquestes són capaces de resoldre. La teoria d'autòmats està íntimament relacionada amb la teoria del llenguatge formal, ja que els autòmats es classifiquen sovint per les classes de llenguatges formals que són capaces de reconèixer. Un autòmat és un model matemàtic per una màquina d'estats finits (FSM en les seves sigles en anglès). Una FSM és una màquina que, donada una entrada de símbols, "salta" a través d'una sèrie d'estats d'acord amb una funció de transició (que pot ser expressada com una taula). Si la màquina d'estats és del tipus anomenat "Mealy", aquesta funció de transició depèn de l'estat en què es troba la màquina i dels símbols d'entrada. L'entrada és llegida símbol a símbol, fins que és "consumida" completament (es pot pensar com una cinta amb una sèrie de símbols escrits, que es va llegint per un capçal lector; el capçal es mou al llarg de la cita, llegint un símbol a cada pas) un cop la cinta s'esgota, l'autòmat es deté. Depenent de l'estat en el que l'autòmat finalitza es diu que aquest ha acceptat o rebutjat l'entrada. Si la FSM acaba en un estat "acceptar", l'autòmat ha acceptat la paraula; i ho fa en un estat "rebutjar", l'autòmat ha rebutjat l'entrada. El conjunt de totes les paraules acceptades per l'autòmat formen el llenguatge acceptat per l'autòmat. (ca) Teorie automatů (anglicky automata theory) je studium a automatů, včetně výpočetních problémů, které mohou být pomocí nich řešené. Jedná se o obor teoretické informatiky, která patří do diskrétní matematiky (předmět studia matematiky i matematické informatiky). Slovo automaty pochází z řeckého slova αὐτόματα, které znamená „samočinný“. Obrázek vpravo znázorňuje konečný automat, který patří k dobře známému typu automatů. Tento automat sestává ze (reprezentovaných na obrázku kružnicemi) a přechodů (reprezentovaných šipkami). Když automat načte symbol ze vstupu, provede přechod (nebo skok) do jiného stavu, podle své přechodové funkce, která má jako parametry aktuální stav a načtený symbol. Teorie automatů má těsnou souvislost s teorií formálních jazyků. Automat je konečnou reprezentací formálního jazyka, který může obsahovat nekonečný počet slov. Automaty jsou často klasifikovány třídou formálních jazyků, kterou mohou rozpoznat. Automaty hrají hlavní roli v , při , v umělé inteligenci, syntaktické analýze a formální verifikaci. (cs) نظرية التشغيل الذاتي أو نظرية الآلات ذاتية التشغيل أو نظرية الآلات المجرّدة (بالإنجليزية: Automata Theory) هي نظرية تهتم بتعريف ودراسة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحاسوبيّة في وقتنا الحالي، وتستخدم بكثرة كأداة للبرهان الرياضي الحاسوبي، لذلك فهي تعتبر من أهمّ ركائز علوم الحاسوب النظرية . (ar) Στη Θεωρητική πληροφορική, θεωρία αυτομάτων είναι η μελέτη των που ονομάζονται ή αυτόματα και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά. Το σχήμα δεξιά παρουσιάζει μια , η οποία ανήκει σε μια γνωστή κατηγορία αυτομάτων. Το αυτόματο αυτό αποτελείται από (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση (ή πήδημα) σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους). Η θεωρία αυτομάτων είναι πολύ σχετική με τη θεωρία τυπικών γλωσσών.Ένα αυτόματο είναι η πεπερασμένη περιγραφή μιας τυπικής γλώσσας, η οποία μπορεί να είναι άπειρο σύνολο.Τα αυτόματα συνήθως κατηγοριοποιούνται ανάλογα με το είδος της τυπικής γλώσσας που αναγνωρίζουν. Τα αυτόματα παίζουν σημαντικό ρόλο στη θεωρία υπολογισμού, τη σχεδίαση μεταγλωττιστών, και την τυπική επαλήθευση. (el) Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments. Automata theory is closely related to formal language theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the Chomsky hierarchy, which describes a nesting relationship between major classes of automata. Automata play a major role in the theory of computation, compiler construction, artificial intelligence, parsing and formal verification. (en) Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt. Sie ist ein wichtiges Werkzeug der Berechenbarkeitstheorie und Komplexitätstheorie. Praktische Anwendung findet sie beim Entwurf von lexikalischen Scannern und Parsern im Compilerbau sowie für den Entwurf von Programmiersprachen. Die Automatentheorie befasst sich mit formalen Sprachen und formalen Grammatiken, die u. a. durch die Chomsky-Hierarchie typisiert werden, und mit Modellen für Automaten, die solche Sprachen verarbeiten können, insbesondere endliche Automaten, Kellerautomaten, Zellularautomaten und Turingmaschinen. (de) La teoría de autómatas es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. También son de gran utilidad en la teoría de la complejidad computacional. Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo. La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene. Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si este termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo. (es) Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar.Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. (in) オートマトン (単数形: 英: automaton [ɔːˈtɑməˌtɑn], 複数形: オートマタ（automata [ɔːˈtɑmətə]）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。 (ja) En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul. Cette théorie est le fondement de plusieurs branches importantes de l'informatique théorique, comme : * La calculabilité, par le modèle des machines de Turing ; * Les automates finis, et leurs variantes, qui sont utilisés dans l'analyse des langues naturelles, la traduction des programmes par les compilateurs, divers algorithmes de manipulation de textes comme les algorithmes de recherche de sous-chaîne, ou la vérification automatique du fonctionnement de circuits logiques; * La théorie de la complexité des algorithmes, visant à classifier les algorithmes en fonction des ressources temporelles et en mémoire nécessaires à leur exécution ; * La vérification de modèle qui sert à établir la conformité de programmes à leurs spécifications. Voir par exemple Coq. Les automates n'ont pas d'existence physique, mais sont un modèle abstrait. (fr) 오토마타 이론(영어: Automata Theory)은 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야이다. 여기서 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계라고 부른다. 이 이름은 '자동'을 의미하는 그리스어 'αὐτόματα'에서 유래하였다. 일반적으로 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다. 이는 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다. 는 일반적으로 오토마타의 능력에 맞게 결정 문제로 환산되며, 이 때 추상 기계와 형식 언어, 형식 문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층 분류를 갖는다. 오토마톤 이론이란 오토마톤을 연구하는 학문이지만, 다른 표현 방식을 빌린다면 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’에 관계되는 것이다. 그리고 대상의 구성요소의 성질 등에는 그리 관여하지 않는다. 오토마타는 컴퓨터 구조 설계와 컴파일러 설계, 파싱, 의 등의 중요한 요소다. (ko) Teoria automatów – dziedzina informatyki zajmująca się badaniem automatów, czyli modeli maszyn liczących. Podstawowym modelem rozważanym w teorii automatów jest automat skończony (automat Moore’a) w różnych wersjach oraz jego rozszerzenia: maszyna RAM, maszyna Turinga, i inne. Istnieje związek teorii automatów z teorią języków formalnych i gramatyk formalnych. (pl) Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма. Существует алгебраическая трактовка теории автоматов, использующая полукольца, формальные степенные ряды, формальные ряды над деревьями, теорию неподвижных точек и теорию матриц. (ru) Inom automatteori studerar man matematiska modeller för utförande av beräkningar, allmänt kallade . Gemensamt för modellerna är att alla accepterar en mängd indata, genomför beräkningen och redovisar resultatet genom att leverera en mängd utdata. Automaten startar i ett väldefinierat starttillstånd och genomgår en serie av tillståndsförändringar, kallade exekvering, enligt ett förutbestämt program. Om automaten under exekveringen når ett bestämt stopptillstånd så stannar automaten och utdata blir tillgänglig för en utomstående observatör. Inom automatteorin studeras flera olika modeller för automater med olika egenskaper och olika beräkningsförmåga, de vanligaste modellerna är dock finita automater, eller , samt Turingmaskiner. Beräkningsmodellerna inom automatteori ligger som grund för imperativa programspråk. (sv) Teoria dos autômatos é o estudo das máquinas abstratas ou autômatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos. É objeto de estudo tanto da Ciência da Computação Teórica como da Matemática Discreta. A palavra autômato vem da palavra grega αὐτόματα que significa “autuação” (em tradução livre), isto é, sem influência externa. A figura ao lado ilustra uma máquina de estados finito, que pertence a uma variedade bem conhecida de autômato. Este autômato consiste em estados (representados na figura por círculos), e transições (representadas por setas). Quando o autômato recebe um símbolo de entrada, ele faz uma transição (ou salto) para outro estado, de acordo com sua função de transição (que tem como entradas o estado atual e o símbolo recente).Teoria dos autômatos também está profundamente relacionada à teoria das linguagens formais. Um autômato é uma representação finita de uma linguagem formal que pode ser um conjunto infinito. Autômatos são frequentemente classificados pela classe das linguagens formais que são capazes de reconhecer, tipicamente ilustrado pela hierarquia de Chomsky, que descreve as relações entre várias línguas e tipos de lógica formalizada. Autômatos desempenham um papel importante em teoria da computação, elaboração de compiladores, inteligência artificial, análise sintática e verificação formal. (pt) 在理论计算机科学中，自动机理论是对抽象机和它们能解决的问题的研究。自动机理论密切关联于形式语言理论，因为自动机经常按它们所能识别的形式语言类来分类。 (zh) Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики.[джерело?] (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/DFAexample.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.augeas.net/libfa/index.html http://www.brics.dk/automaton https://archive.org/details/computationautom0000salo https://archive.org/details/computationfinit0000mins |
| dbo:wikiPageID | 103356 (xsd:integer) |
| dbo:wikiPageLength | 32442 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102545499 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Probabilistic_Turing_machine dbr:Pushdown_automaton dbr:Queue_(abstract_data_type) dbr:Elaine_Rich dbr:Electronic_lock dbr:Myhill–Nerode_theorem dbr:Nondeterministic_Turing_machine dbr:Monoidal_category dbr:Parsing dbr:Jeffrey_D._Ullman dbr:Boolean_differential_calculus dbr:Deterministic_Finite_Automaton dbr:John_von_Neumann dbr:Regular_languages dbr:Deterministic_automaton dbr:Deterministic_context-free_language dbr:Deterministic_pushdown_automaton dbr:Induction_of_regular_languages dbr:Information_system dbr:Programming_language_specification dbr:Weighted_automaton dbr:Combinational_logic dbr:Compiler_construction dbr:Context-free_grammar dbr:An_Introduction_to_Cybernetics dbr:Omega_language dbr:Systems_theory dbr:Turing_machine_equivalents dbr:Pumping_lemma_for_regular_languages dbr:Clarendon_Press dbr:Claude_Shannon dbr:Edward_F._Moore dbr:Edward_Fredkin dbr:Monoid dbr:Context-free_language dbr:Context-sensitive_language dbr:Conway's_Game_of_Life dbr:Alphabet_(computer_science) dbr:Limit_(category_theory) dbr:Stack_(abstract_data_type) dbr:Stephen_Cole_Kleene dbr:Computational_complexity dbr:Computational_problem dbr:Functional_completeness dbr:State_(computer_science) dbr:Streett_automaton dbr:Symbol_(formal) dbr:Symbolic_language_(programming) dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:2-category dbr:Büchi_automaton dbr:Tree_(automata_theory) dbr:Tree_automaton dbr:W._Ross_Ashby dbr:Countable dbr:Irreducible_polynomial dbr:Linear_bounded_automaton dbr:Log-space_transducer dbr:Semigroup dbr:Recursively_enumerable_language dbr:DFA_minimization dbr:Dana_Scott dbr:Finite-state_transducer dbr:Finite_field dbr:Formal_languages dbr:Formal_verification dbr:Noam_Chomsky dbr:Norbert_Wiener dbr:Formal_language dbr:Probability dbr:Recognizable_language dbr:Regular_language dbr:Hybrid_automaton dbr:The_Human_Use_of_Human_Beings dbr:Artificial_intelligence dbr:Artificial_life dbr:Abstract_algebra dbr:Abstract_machine dbc:Automata_(computation) dbr:Chapman_&_Hall dbr:Chomsky_hierarchy dbr:John_Horton_Conway dbr:System dbr:Effective_method dbr:Differential_calculus dbr:Automaton dbr:Marvin_Minsky dbr:Groupoid dbr:Pushdown_automata dbr:Metric_automata dbr:Igor_Aleksander dbr:Konrad_Zuse dbr:Michael_O._Rabin dbr:Michael_Sipser dbr:Omega-regular_language dbr:Cartesian_closed_category dbr:Category_(mathematics) dbr:Rabin_automaton dbr:Rajeev_Motwani dbr:Set_theory dbr:Cellular_automata dbr:Turing_machine dbr:Infinite_tree_automaton dbr:Text_processing dbr:Nondeterministic_Finite_Automaton dbr:Natural_language dbr:Finite-state_machine dbr:Muller_automaton dbr:Multitape_Turing_machine dbr:Linear_bounded_automata dbr:Transition_table dbr:Word_(mathematics) dbr:Hardware_design dbr:Parity_automaton dbr:Analog_automata dbr:Finite_automata dbr:Finite_automaton dbr:John_E._Hopcroft dbr:John_M._Howie dbr:Queue_machine dbr:Alternating_automaton dbr:Formal_grammars dbr:Deterministic_Turing_machine dbr:N-tuple dbr:Colimit dbr:Omega_automaton dbr:Categories_of_groupoids dbr:Continuous_automata dbr:David_T._Barnard dbr:File:DFAexample.svg dbr:Geometric_automata dbr:Groupoid_category dbr:James_P._Schmeiser dbr:Nondeterministic_Push_Down_Automaton dbr:Sequential_machine |
| dbp:cs1Dates | y (en) |
| dbp:date | May 2019 (en) |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Cite_book dbt:ISBN dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Computer_science dbt:Mr dbt:Industrial_and_applied_mathematics dbt:Formal_languages_and_grammars dbt:Automata_theory |
| dcterms:subject | dbc:Automata_(computation) |
| gold:hypernym | dbr:Study |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 dbo:Book yago:WikicatFormalLanguages |
| rdfs:comment | نظرية التشغيل الذاتي أو نظرية الآلات ذاتية التشغيل أو نظرية الآلات المجرّدة (بالإنجليزية: Automata Theory) هي نظرية تهتم بتعريف ودراسة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحاسوبيّة في وقتنا الحالي، وتستخدم بكثرة كأداة للبرهان الرياضي الحاسوبي، لذلك فهي تعتبر من أهمّ ركائز علوم الحاسوب النظرية . (ar) Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar.Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. (in) オートマトン (単数形: 英: automaton [ɔːˈtɑməˌtɑn], 複数形: オートマタ（automata [ɔːˈtɑmətə]）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。 (ja) Teoria automatów – dziedzina informatyki zajmująca się badaniem automatów, czyli modeli maszyn liczących. Podstawowym modelem rozważanym w teorii automatów jest automat skończony (automat Moore’a) w różnych wersjach oraz jego rozszerzenia: maszyna RAM, maszyna Turinga, i inne. Istnieje związek teorii automatów z teorią języków formalnych i gramatyk formalnych. (pl) Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма. Существует алгебраическая трактовка теории автоматов, использующая полукольца, формальные степенные ряды, формальные ряды над деревьями, теорию неподвижных точек и теорию матриц. (ru) 在理论计算机科学中，自动机理论是对抽象机和它们能解决的问题的研究。自动机理论密切关联于形式语言理论，因为自动机经常按它们所能识别的形式语言类来分类。 (zh) Тео́рія автома́тів — логіко-математична теорія, об'єктом дослідження якої є абстрактні автомати — покрокові перетворювачі інформації; розділ кібернетики.[джерело?] (uk) La teoria d'autòmats és una branca de les ciències de la computació que estudia les màquines abstractes i els problemes que aquestes són capaços de resoldre. Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, compilador és, disseny de maquinari i intel·ligència artificial. La teoria d'autòmats està estretament relacionada amb la teoria del llenguatge formal, ja que els autòmats són classificats sovint per la classe de llenguatges formals que són capaços de reconèixer. (ca) La teoria d'autòmats és una branca de les ciències de la computació que estudia les màquines abstractes i els problemes que aquestes són capaces de resoldre. La teoria d'autòmats està íntimament relacionada amb la teoria del llenguatge formal, ja que els autòmats es classifiquen sovint per les classes de llenguatges formals que són capaces de reconèixer. (ca) Teorie automatů (anglicky automata theory) je studium a automatů, včetně výpočetních problémů, které mohou být pomocí nich řešené. Jedná se o obor teoretické informatiky, která patří do diskrétní matematiky (předmět studia matematiky i matematické informatiky). Slovo automaty pochází z řeckého slova αὐτόματα, které znamená „samočinný“. Teorie automatů má těsnou souvislost s teorií formálních jazyků. Automat je konečnou reprezentací formálního jazyka, který může obsahovat nekonečný počet slov. Automaty jsou často klasifikovány třídou formálních jazyků, kterou mohou rozpoznat. (cs) Στη Θεωρητική πληροφορική, θεωρία αυτομάτων είναι η μελέτη των που ονομάζονται ή αυτόματα και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά. Το σχήμα δεξιά παρουσιάζει μια , η οποία ανήκει σε μια γνωστή κατηγορία αυτομάτων. Το αυτόματο αυτό αποτελείται από (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση (ή πήδημα) σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους). (el) Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of inpu (en) Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt. Sie ist ein wichtiges Werkzeug der Berechenbarkeitstheorie und Komplexitätstheorie. Praktische Anwendung findet sie beim Entwurf von lexikalischen Scannern und Parsern im Compilerbau sowie für den Entwurf von Programmiersprachen. (de) La teoría de autómatas es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. También son de gran utilidad en la teoría de la complejidad computacional. (es) En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul. Cette théorie est le fondement de plusieurs branches importantes de l'informatique théorique, comme : Les automates n'ont pas d'existence physique, mais sont un modèle abstrait. (fr) 오토마타 이론(영어: Automata Theory)은 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야이다. 여기서 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계라고 부른다. 이 이름은 '자동'을 의미하는 그리스어 'αὐτόματα'에서 유래하였다. 일반적으로 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다. 이는 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다. 는 일반적으로 오토마타의 능력에 맞게 결정 문제로 환산되며, 이 때 추상 기계와 형식 언어, 형식 문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층 분류를 갖는다. (ko) Teoria dos autômatos é o estudo das máquinas abstratas ou autômatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos. É objeto de estudo tanto da Ciência da Computação Teórica como da Matemática Discreta. A palavra autômato vem da palavra grega αὐτόματα que significa “autuação” (em tradução livre), isto é, sem influência externa. Autômatos desempenham um papel importante em teoria da computação, elaboração de compiladores, inteligência artificial, análise sintática e verificação formal. (pt) Inom automatteori studerar man matematiska modeller för utförande av beräkningar, allmänt kallade . Gemensamt för modellerna är att alla accepterar en mängd indata, genomför beräkningen och redovisar resultatet genom att leverera en mängd utdata. Automaten startar i ett väldefinierat starttillstånd och genomgår en serie av tillståndsförändringar, kallade exekvering, enligt ett förutbestämt program. Om automaten under exekveringen når ett bestämt stopptillstånd så stannar automaten och utdata blir tillgänglig för en utomstående observatör. (sv) |
| rdfs:label | Automata theory (en) نظرية التشغيل الذاتي (ar) Teoria d'autòmats (ca) Teoria d'Autòmats (ca) Teorie automatů (cs) Automatentheorie (de) Θεωρία αυτομάτων (el) Teoría de autómatas (es) Teori otomata (in) Théorie des automates (fr) 오토마타 이론 (ko) オートマトン (ja) Teoria automatów (pl) Teoria dos autômatos (pt) Теория автоматов (ru) Automatteori (sv) Теорія автоматів (uk) 自動機理論 (zh) |
| owl:sameAs | freebase:Automata theory yago-res:Automata theory http://d-nb.info/gnd/4003953-5 wikidata:Automata theory wikidata:Automata theory dbpedia-ar:Automata theory http://bs.dbpedia.org/resource/Teorija_automata dbpedia-ca:Automata theory dbpedia-ca:Automata theory dbpedia-cs:Automata theory dbpedia-de:Automata theory dbpedia-el:Automata theory dbpedia-es:Automata theory dbpedia-fa:Automata theory dbpedia-fi:Automata theory dbpedia-fr:Automata theory dbpedia-he:Automata theory http://hi.dbpedia.org/resource/ऑटोमेटा_सिद्धांत dbpedia-hr:Automata theory dbpedia-id:Automata theory dbpedia-ja:Automata theory dbpedia-kk:Automata theory dbpedia-ko:Automata theory dbpedia-mk:Automata theory dbpedia-nn:Automata theory dbpedia-no:Automata theory dbpedia-pl:Automata theory dbpedia-pt:Automata theory dbpedia-ro:Automata theory dbpedia-ru:Automata theory dbpedia-sh:Automata theory dbpedia-simple:Automata theory dbpedia-sk:Automata theory dbpedia-sr:Automata theory dbpedia-sv:Automata theory http://tg.dbpedia.org/resource/Назарияи_автоматҳо dbpedia-th:Automata theory http://tl.dbpedia.org/resource/Teorya_ng_automata dbpedia-tr:Automata theory dbpedia-uk:Automata theory dbpedia-vi:Automata theory dbpedia-zh:Automata theory https://global.dbpedia.org/id/FErh |
| prov:wasDerivedFrom | wikipedia-en:Automata_theory?oldid=1102545499&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DFAexample.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Automata_theory |
| is dbo:academicDiscipline of | dbr:Juhani_Karhumäki dbr:Viliam_Geffert dbr:Descriptional_Complexity_of_Formal_Systems dbr:International_Conference_on_Reachability_Problems dbr:Maxime_Crochemore dbr:Conference_on_Implementation_and_Application_of_Automata dbr:Thomas_Colcombet dbr:Kai_Salomaa dbr:Mikołaj_Bojańczyk |
| is dbo:knownFor of | dbr:Abraham_Ginzburg dbr:Dana_Scott dbr:Oscar_H._Ibarra |
| is dbo:wikiPageDisambiguates of | dbr:Automata_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Applications_of_automata_theory dbr:Automata_Theory dbr:Automaton_theory dbr:Analog_automata dbr:Theory_of_automata |
| is dbo:wikiPageWikiLink of | dbr:Powerset_construction dbr:Pushdown_automaton dbr:Samuel_Eilenberg dbr:Elaine_Rich dbr:Eli_Shamir dbr:Epiphenomenalism dbr:List_of_academic_fields dbr:List_of_computer_science_conferences dbr:List_of_computer_scientists dbr:Nondeterministic_finite_automaton dbr:Binary_relation dbr:Boolean_differential_calculus dbr:Branches_of_science dbr:Brenda_Baker dbr:David_L._Dill dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Aperiodic_finite_state_automaton dbr:Aperiodic_semigroup dbr:Joseph_Goguen dbr:Juhani_Karhumäki dbr:List_of_pioneers_in_computer_science dbr:Regular_expression dbr:Reo_Coordination_Language dbr:Reversible_cellular_automaton dbr:Richard_E._Ladner dbr:Unbounded_nondeterminism dbr:University_of_Rijeka dbr:Viliam_Geffert dbr:De_Bruijn_sequence dbr:Derick_Wood dbr:Descriptional_Complexity_of_Formal_Systems dbr:Deterministic_acyclic_finite_state_automaton dbr:Deterministic_automaton dbr:Deterministic_pushdown_automaton dbr:Dexter_Kozen dbr:Index_of_philosophy_articles_(A–C) dbr:Index_of_software_engineering_articles dbr:Informatics dbr:Input/output_automaton dbr:International_Conference_on_Reachability_Problems dbr:Intersection_non-emptiness_problem dbr:Introduction_to_Automata_Theory,_Languages,_and_Computation dbr:JFLAP dbr:Rajeev_Alur dbr:Semigroup_action dbr:List_of_mathematical_theories dbr:List_of_people_from_Negros_Occidental dbr:Combinational_logic dbr:Computability dbr:Maxime_Crochemore dbr:Mehryar_Mohri dbr:SPIN_model_checker dbr:Generalized_Büchi_automaton dbr:Generative_science dbr:Thread_automaton dbr:Freeman_Dyson dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Government_Engineering_College,_Trivandrum dbr:Graph_labeling dbr:Boundedly_generated_group dbr:Monoid dbr:Conference_on_Implementation_and_Application_of_Automata dbr:Thomas_Colcombet dbr:Thomas_N._Hibbard dbr:Dana_Angluin dbr:Epsilon dbr:Orna_Kupferman dbr:Android_(robot) dbr:Applications_of_automata_theory dbr:Leslie_Valiant dbr:Calculating_Space dbr:Standard_Generalized_Markup_Language dbr:Suffix_automaton dbr:Combinatorics dbr:Complementation_of_Büchi_automaton dbr:Complexity dbr:Computational_linguistics dbr:Computer_science dbr:Hardware_security dbr:Harlan_Mills dbr:Journal_of_Automata,_Languages_and_Combinatorics dbr:Krohn–Rhodes_theory dbr:Petri_net dbr:State_(computer_science) dbr:Tagged_Deterministic_Finite_Automaton dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:Mathematical_and_theoretical_biology dbr:McNaughton's_theorem dbr:Michael_W._Shields dbr:1959_in_science dbr:Automata_Theory dbr:Büchi_automaton dbr:Tree_(automata_theory) dbr:Tree_stack_automaton dbr:UP_Diliman_Department_of_Computer_Science dbr:Learning_automaton dbr:Unrestricted_grammar dbr:Abraham_Ginzburg dbr:Actor_model dbr:D._S._Malik dbr:DFA_minimization dbr:Dana_Scott dbr:Dartmouth_workshop dbr:Alphabet_(formal_languages) dbr:Alternating_finite_automaton dbr:Alternating_timed_automaton dbr:Alternating_tree_automata dbr:Faron_Moller dbr:Noam_Chomsky dbr:Oscar_H._Ibarra dbr:Cellular_automaton dbr:Chu_space dbr:Discrete_event_dynamic_system dbr:Discrete_mathematics dbr:Formal_grammar dbr:Formal_language dbr:Formal_methods dbr:History_of_artificial_life dbr:History_of_computing_in_Poland dbr:Knuth–Morris–Pratt_algorithm dbr:Marek_Chrobak dbr:List_of_Iranian_Americans dbr:Ludwig_Staiger dbr:Recognizable_set dbr:Gremlin_(query_language) dbr:Grigore_Moisil dbr:Group_homomorphism dbr:Géraud_Sénizergues dbr:Harry_R._Lewis dbr:Astrochicken dbr:Janusz_Brzozowski_(computer_scientist) dbr:Jean-Éric_Pin dbr:Jeffrey_Ullman dbr:Taylor_Booth_(mathematician) dbr:Courcelle's_theorem dbr:Temporal_logic dbr:Hybrid_automaton dbr:Hybrid_system dbr:Jeffrey_Shallit dbr:Ω-automaton dbr:State-transition_table dbr:Armin_B._Cremers dbr:Arto_Salomaa dbr:Jetty_Kleijn dbr:Kai_Salomaa dbr:Co-Büchi_automaton dbr:Cobham's_theorem dbr:Torsion_group dbr:Transition_system dbr:Word_(disambiguation) dbr:Star_height dbr:Regular_numerical_predicate dbr:Ding-Zhu_Du dbr:Automata-based_programming dbr:Automaton dbr:Avraham_Trahtman dbr:Marcel-Paul_Schützenberger dbr:Büchi_arithmetic dbr:Square-free_word dbr:Free_monoid dbr:GrowCut_algorithm dbr:Guarded_logic dbr:Imre_Simon dbr:Information_technology dbr:Krishnendu_Chatterjee dbr:Merton_College,_Oxford dbr:Middle_Eastern_Americans dbr:Mikołaj_Bojańczyk dbr:Nataša_Jonoska dbr:Automata_(disambiguation) dbr:Automaton_(disambiguation) dbr:RE2_(software) dbr:Sergey_Yablonsky dbr:Seymour_Ginsburg dbr:Christel_Baier dbr:Kleene_star dbr:Véronique_Bruyère dbr:Monadic_second-order_logic dbr:Shmuel_Safra dbr:Wojciech_Rytter dbr:Unambiguous_finite_automaton dbr:VPA dbr:Variety_(cybernetics) dbr:Von_Neumann_universal_constructor dbr:Nested_word dbr:F-coalgebra dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Word_metric dbr:Finite-state_machine dbr:NFA_minimization dbr:Think-a-Dot dbr:Muller_automaton dbr:Pebble_automaton dbr:Weak_Büchi_automaton dbr:Subshift_of_finite_type dbr:Self-verifying_finite_automaton dbr:Signal_(model_checking) dbr:Signal_automaton dbr:Noncommutative_signal-flow_graph dbr:Palindrome dbr:Permutation_automaton dbr:Semi-deterministic_Büchi_automaton dbr:The_Tower_of_Hanoi_–_Myths_and_Maths dbr:Word_Processing_in_Groups dbr:Outline_of_academic_disciplines dbr:Outline_of_computer_science dbr:Outline_of_discrete_mathematics dbr:Outline_of_formal_science dbr:Substitution_tiling dbr:Transformation_semigroup dbr:Sequential_logic dbr:Rational_set dbr:Science_and_technology_in_Russia dbr:Turing_completeness dbr:Supratik_Chakraborty dbr:Věra_Trnková dbr:Two-way_finite_automaton dbr:Automaton_theory dbr:Timed_automaton dbr:Analog_automata dbr:Theory_of_automata |
| is dbp:field of | dbr:Juhani_Karhumäki dbr:Viliam_Geffert dbr:Maxime_Crochemore dbr:Kai_Salomaa |
| is dbp:fields of | dbr:Mikołaj_Bojańczyk |
| is foaf:primaryTopic of | wikipedia-en:Automata_theory |
