Definition
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 with close connections to cognitive science and mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton 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 and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.
Related concepts
2-categoryACM Computing Classification SystemAbstract algebraAbstract machineAlgebra of physical spaceAlgebraic structureAlgorithmAlgorithm designAlgorithmic efficiencyAlphabet (computer science)Alternating automatonAn Introduction to CyberneticsAnalog automataAnalysis of algorithmsAnalytical mechanicsAnil NerodeAperiodic finite state automatonApplication securityApplied mathematicsApproximation theoryArtificial intelligenceArtificial lifeArto SalomaaAugmented realityAutomata theoryAutomated planning and schedulingAutomated theorem provingAutomatonBoolean differential calculusBosonic string theoryBüchi automatonCalculus of variationsCambridge University PressCartesian closed categoryCategories for the Working MathematicianCategories of groupoidsCategory (mathematics)Cellular automataChaos theoryChapman & HallChomsky hierarchyClarendon PressClassical field theoryClaude ShannonClifford algebraClifford analysisCoding theoryCognitive scienceColimitCombinational logicCombinatoricsCommunication protocolCompiler constructionComputability theoryComputational biologyComputational chemistryComputational complexityComputational complexity theoryComputational engineeringComputational geometryComputational intelligenceComputational mathematicsComputational number theoryComputational physicsComputational problemComputational social scienceComputational statisticsComputer accessibilityComputer algebraComputer animationComputer architectureComputer data storageComputer graphicsComputer hardwareComputer networkComputer scienceComputer securityComputer visionComputingComputing deviceComputing platformConcurrency (computer science)Concurrent computingConformal field theoryConstraint programmingConstraint satisfaction problemContext-free grammarContext-free languageContext-sensitive grammarContext-sensitive languageContinuous automatonControl flowControl theoryConway's Game of LifeCountableCross-validation (statistics)CryptographyCyber-physical systemCyberwarfareDFA minimizationDana ScottData miningDatabaseDavid T. BarnardDecider (Turing machine)Decision support systemDecision theoryDependabilityDeterministic Finite AutomatonDeterministic Turing machineDeterministic acyclic finite state automatonDeterministic automatonDeterministic context-free grammarDeterministic context-free languageDeterministic pushdown automatonDifferential calculusDifferential equationDifferential formDifferential geometryDigital artDigital libraryDigital marketingDiscrete geometryDiscrete mathematicsDistributed artificial intelligenceDistributed computingDocument management systemDomain-specific languageDynamical systemE-commerceEducational technologyEdward F. MooreEdward FredkinEffective field theoryEffective methodElaine RichElectronic design automationElectronic lockElectronic publishingElectronic votingEmbedded pushdown automatonEmbedded systemEnterprise information systemEnterprise softwareEuropean Community on Computational Methods in Applied SciencesExterior algebraExterior calculusFault toleranceField theory (physics)Finite-state machineFinite-state transducerFinite automataFinite automatonFinite fieldFinite languageForm factor (design)Formal grammarFormal grammarsFormal languageFormal languagesFormal methodsFormal verificationFourier analysisFunctional analysisFunctional completenessFunctional integrationGame theoryGauge theoryGauge theory (mathematics)Geographic information systemGeometric algebraGeometric analysisGeometric automataGeometric calculusGraph theoryGraphics processing unitGreek languageGreen computingGroupoidGroupoid categoryHamiltonian mechanicsHardware accelerationHardware designHardware securityHarmonic analysis (mathematics)Health informaticsHuman-centered computingHuman–computer interactionHybrid automatonIgor AleksanderImage compressionIndexed grammarIndexed languageInduction of regular languagesIndustrial process controlInfinite tree automatonInformation retrievalInformation securityInformation systemInformation theoryIntegrated circuitIntegrated development environmentInteraction designInternational Council for Industrial and Applied MathematicsInterpreter (computing)Introduction to Automata Theory, Languages, and ComputationIntroduction to the Theory of ComputationIntrusion detection systemIrreducible polynomialJames P. SchmeiserJapan Society for Industrial and Applied MathematicsJeffrey UllmanJohn HopcroftJohn Horton ConwayJohn M. HowieJohn von NeumannJuris HartmanisKnowledge representation and reasoningKonrad ZuseLagrangian mechanicsLibrary (computing)Limit (category theory)Linear bounded automataLinear bounded automatonLinear context-free rewriting languageLinear context-free rewriting systemList of arbitrary-precision arithmetic softwareList of computer size categoriesList of finite element software packagesList of interactive geometry softwareList of mathematics topicsList of numerical-analysis softwareList of optimization softwareList of statistical softwareLog-space transducerLogic in computer scienceMachine learningMalliavin calculusMarvin MinskyMathematical analysisMathematical and theoretical biologyMathematical chemistryMathematical economicsMathematical financeMathematical logicMathematical optimizationMathematical physicsMathematical psychologyMathematical sociologyMathematical softwareMathematicsMetric automataMichael O. RabinMichael SipserMiddlewareMobile computingModel of computationModeling languageMonoidMonoidal categoryMuller automatonMulti-task learningMultilinear algebraMultimedia databaseMultiprocessingMultitape Turing machineMultithreading (computer architecture)Multivariable calculusMyhill–Nerode theoremN-tupleNatural languageNatural language processingNested stack automatonNested wordNetwork architectureNetwork performanceNetwork schedulerNetwork securityNetwork serviceNetworking hardwareNoam ChomskyNon-recursive grammarNondeterministic Finite AutomatonNondeterministic Push Down AutomatonNondeterministic Turing machineNorbert WienerNumerical analysisNumerical linear algebraNumerical methods for ordinary differential equationsNumerical methods for partial differential equationsOmega-regular languageOmega automatonOmega languageOpen sourceOperating systemOperations researchOperator algebraOperator theoryOrdinary differential equationOutline of computer sciencePTIMEParallel computingParameter (computer programming)Parity automatonParsingPartial differential equationParticle physics and representation theoryPath integral formulationPeripheralPerturbation theoryPerturbation theory (quantum mechanics)Petri netPhilosophy of artificial intelligencePhotograph manipulationPoisson algebraPotential theoryPrinted circuit boardProbabilistic Turing machineProbabilityProbability distributionProbability theoryProcessor (computing)Programming languageProgramming language specificationProgramming language theoryProgramming paradigmProgramming teamProgramming toolProper subsetPumping lemma for regular languagesPushdown automataPushdown automatonQuantum computingQuantum field theoryQuantum finite automatonQuantum groupQueue (abstract data type)Queue machineRabin automatonRajeev MotwaniRandom variableRandomized algorithmRange concatenation grammarsRange concatenation languageReal-time computingRecognizable languageRecursive languageRecursively enumerable languageRegular grammarRegular languageRegular languagesReinforcement learningRendering (computer graphics)Renormalization groupRequirements analysisRichard E. StearnsSaunders Mac LaneSecurity hackerSecurity service (telecommunication)Semantics (computer science)SemigroupSequential machineSet theorySocial choice theorySocial computingSocial softwareSociety for Industrial and Applied MathematicsSociété de Mathématiques Appliquées et IndustriellesSoftware configuration managementSoftware constructionSoftware deploymentSoftware designSoftware developmentSoftware development processSoftware engineeringSoftware frameworkSoftware maintenanceSoftware qualitySoftware repositorySolid modelingSolverSpacetime algebraStack (abstract data type)Star-free languageState (computer science)State diagramStatistical field theoryStatisticsStephen Cole KleeneStochastic calculusStochastic computingStochastic differential equationStochastic processStreett automatonString theorySuperalgebraSupersymmetric quantum mechanicsSupersymmetric theory of stochastic dynamicsSupersymmetrySupersymmetry algebraSupervised learningSymbol (formal)Symbolic language (programming)SystemSystem on a chipSystems theoryTensorTensor calculusTensor softwareText processingThe Human Use of Human BeingsThe Unreasonable Effectiveness of Mathematics in the Natural SciencesTheoretical computer scienceTheory of computationThread automatonTopic outline of mathematicsTopological field theoryTopological string theoryTransition (computer science)Transition tableTree-adjoining grammarTree (automata theory)Tree automatonTree stack automatonTuring machineTuring machine equivalentsTwo-way finite automatonUbiquitous computingUnrestricted grammarUnsupervised learningValidated numericsVector calculusVery-large-scale integrationVideo gameVirtual machineVirtual realityVisualization (graphics)Věra TrnkováW. Ross AshbyWeighted automatonWireless sensor networkWord (mathematics)Word processorWorld Wide Web
44 concepts already in your glossary