automátas

Automata, sometimes referred to as automatas in some languages, are abstract computational models used to represent and analyze computation. In computer science, automata theory studies how formal languages can be recognized, transformed, or decided by mechanical processes.

Finite automata, both deterministic (DFA) and nondeterministic (NFA), have a finite number of states and read input strings symbol by symbol. They recognize regular languages. Pushdown automata (PDA) extend finite automata with a stack, enabling recognition of context-free languages. Turing machines, which include a read-write tape, capture the power of general computation and characterize recursively enumerable languages. A related spectrum includes linear-bounded automata, which constrain the tape size and fall between PDAs and Turing machines in capability.

Key results in automata theory include the equivalence of DFAs and NFAs in terms of recognized languages, the closure properties of regular languages, and the central role of Turing machines in the Church–Turing thesis. In many cases, deterministic and nondeterministic machines recognize the same class of languages, although nondeterministic representations can be more succinct.

Automata theory has broad practical applications, including lexical analysis and the use of regular expressions in compilers, text processing, protocol verification, formal verification, parsing, and model checking. The field provides a formal toolkit for reasoning about what can be computed, how long it may take, and how complex the required resources are.

Historically, concepts of automata emerged from early formal language studies in the mid-20th century (notably Kleene, Rabin, and Scott) and were connected to broader models of computation by Turing. Today, automata theory remains foundational in theoretical and applied computer science.