Enciclopedia universală

Automat

Automat - Obiect matematic care descrie un dispozitiv utilizat pentru acceptarea limbajelor. Pentru fiecare clasa de limbaje corespunzatoare ierarhiei Chomsky exista cate un tip de automat care poate sa accepte limbaje din clasa respectiva. Cel mai simplu tip de automat este automatul finit. Clasa limbajelor care sunt acceptate de catre automatele finite sunt limbajele regulate (generate de catre gramatici sau expresii regulate). Clasa limbajelor care sunt acceptate de catre automate cu stiva (push down) sunt limbajele independente de context. Limbajele dependente de context sunt acceptate de catre automatele liniar marginite. Cel mai general automat este Masina Turing care accepta limbaje care pot sa fie generate de modelul general de gramatici.