3.4.3.1. Automatele cu numãr finit de stãri. Acestea reprezintã cele mai simple sintaxe generative. Automatele de acest fel sînt maºini a cãror memorie conþine un numãr oarecare de stãri. Stãrile vor fi notate S , S ..., S . Maºina este programatã sã treacã de la o stare 0
1
n
la alta, însã aceastã tranziþie nu se realizeazã decît într-o ordine care este ea însãºi precizatã în program. Fiecare tranziþie înseamnã producerea unui cuvînt. O secvenþã de tranziþii este deci o secvenþã de cuvinte. S reprezintã, de exemplu, tranziþia de la starea iniþialã S la 0-1
0
starea S ºi efectul acestei tranziþii este apariþia cuvîntului copilul. S este tranziþia urmã-1
1-2
toare, fapt care, de pildã, poate însemna apariþia cuvîntului neastîmpãrat º. a. m. d.
În program sînt indicate ºi stãrile finale. O stare finalã este starea care, o datã atinsã, determinã revenirea automatã a maºinii la starea iniþialã S . Maºina a parcurs astfel unul dintre 0
traseele prevãzute în program. Un asemenea traseu este, de fapt, procesul de construcþie a unei propoziþii. În termenii operaþiilor pe care le poate face o asemenea maºinã, o propoziþie este o secvenþã de tranziþii în care ultima tranziþie înseamnã atingerea unei stãri finale.
O schemã posibilã de funcþionare a unui automat cu un numãr finit de stãri este urmãtoarea:
Sintaxa
163
S
*
1
S4
S7
S
*
0
S2
S5
S8
S
*
*
3
S6
S9
S1
S*
10
Stãri:
S = bãiatul
S = fata
S = profesorul
1
2
3
