Enciclopedia universală

Automat finit

Automat finit - Dispozitiv format dintr-o banda de intrare (care contine un sir de simboli) si o unitate de control. Un cap de citire permite citirea simbolurilor de pe banda de intrare si se poate deplasa numai spre dreapta cu cate un simbol. Functionarea unitatii de control pleaca dintr-o stare initiala, cu capul de citire pozitionat pe primul simbol din sirul de intrare. Pe baza starii curente si a simbolului curent de pe banda de intrare automatul trece intr-o noua stare, avansand eventual pe banda de intrare pe urmatorul simbol. Se spune ca automatul a executat o tranzitie. Automatul accepta sirul de intrare daca ajunge intr-o stare finala avand capul de citire dupa ultimul simbol de pe banda de intrare. Multimea sirurilor acceptate de catre un automat finit este limbajul formal acceptat de catre automat. Automatele finite pot sa fie deterministe sau nedeterministe. In cazul unui utomat determinist pentru fiecare combinatie stare curenta, simbol curent pe banda de intrare exista cel mult o singura stare urmatoare si automatul avanseaza pentru fiecare tranzitie. Clasa limbajelor acceptate de catre automatele finite deterministe este identica cu cea acceptata de automatele nedeterministe. Analizoarele lexicale sunt implementate ca simulatoare de automate finite deterministe.