Enciclopedia universală

Automat cu stiva

Automat cu stiva - Dispozitiv format dintr-o banda de intrare (care contine un sir de simboli), o stiva 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 un simbol special de initializare in varful stivei si cu capul de citire pozitionat pe primul simbol din sirul de intrare. Pe baza starii curente, a simbolului curent de pe banda de intrare si a simbolului aflat in varful stivei automatul trece intr-o noua stare, inlocuind simbolul din varful stivei cu un sir de caractere si 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 cu stiva este limbajul formal acceptat de catre automat. Automatele cu stiva pot sa fie deterministe sau nedeterministe. In cazul unui automat determinist pentru fiecare combinatie stare curenta, simbol in varful stivei, simbol curent pe banda de intrare exista cel mult o singura stare urmatoare, sir memorat in stiva, automatul avanseaza pentru fiecare tranzitie. Clasa limbajelor acceptate de catre automatele cu stiva deterministe este o submultime a celei acceptate de catre automatele cu stiva nedeterministe. Analizoarele sintactice sunt implementate ca simulatoare de automate cu stiva.