Având în vedere un alfabet finit
și, astfel, mulțimea tuturor cuvintelor finite din alfabetul:
.
Limba oficială în alfabet - este un subset arbitrar.
Un set de reguli de formare a cuvintelor limbaj formal se numește gramatica. În funcție de complexitatea normelor de limbaje formale sunt împărțite în mai multe clase. În continuare, considerăm că una dintre cele mai simple clase de limbi străine - limbi obișnuite - și să stabilească relația lor cu automate finite.
Luați în considerare un set de limbi cu același alfabet și să introducă operațiuni pe aceste limbi.
1 °. Asociația. Această operațiune set teoretic care, spre deosebire de intersecția și complementul, are o interpretare naturală sintactică:
.
2 °. Concatenarea - o operație asociată cu înlocuirea limbii în limba:
.
3 °. Iterație este definit de limbaj
,
în cazul în care - limbajul format din cuvinte goale, care nu trebuie să fie confundat cu o limbă goală. nu conține un singur cuvânt; . . ...
Limbi. . constând din cuvinte goale sau cu o literă sunt numite elementare.
Limbajul este numit regulat. în cazul în care acesta poate fi construit printr-un număr finit de operații de îmbinare, înlănțuirea și repetare.
35. Aparatul de stat este numit un automaton Moore. în cazul în care funcția de ieșire depinde doar de condiția:
.
Un model general al unei mașini de stare finită, care au fost luate în considerare anterior, se numește un automaton Millie.
În ciuda faptului că mașina Milli - un caz special al mașinii Moore, posibilitatea acestor două mașini sunt aceleași.
Teorema. Pentru orice mașină Milli există acolo un automaton echivalent Moore.
Luați în considerare aparatul Moore, cu două simboluri de ieșire 0 și mașină 1.Takoy este de a oferi câteva cuvinte de intrare 1 la celălalt - 0. Să presupunem că, în primul caz mașina cuvântul „recunoscut“, iar al doilea - nr. Acest lucru determină un limbaj format din cuvinte care pot fi recunoscute în mod automat.
Împărțim aparatul de stat Moore în două clase: - ieșire este egal cu 1, clasa - ieșire este 0. Acest lucru face posibil să se ia în considerare ieșirile funcționale și definesc automaton rezolvator ca sistem
.
Cu fiecare mașină le-am atribui un limbaj ușor de recunoscut
,
că este, o limbă cuprinde toate cuvintele care traduc într-una dintre închiderea automată a stării inițiale.
Exemplu. . în cazul în care. . . . și stabilește masa