Calcul. Sisteme formale.
Formală gramatică. maşini
Există o clasă de probleme, modele matematice și algoritmi ale căror soluții sunt reprezentate convenabil sub formă de calculi formali. Împreună cu mașina de stări și funcții, un algoritm calculat, "algoritmul-calcul" este al treilea tip de rafinament al conceptului algoritmului. Tehnologia de proiectare a programelor, bazată pe calculul formal, are o anumită specificitate, care este discutată în această prelegere.
1. Calculul și sistemele formale
Semnificativ, calculul definește un mod constructiv de generare a cuvintelor dintr-o anumită limbă. De exemplu, calculul diferențelor finite ale lui Newton face posibilă generarea (calcula) pentru o expresie regulată a formulelor cu diferențiale toate expresiile echivalente date de regulile transformărilor de identitate. Calculul propozițiilor permite generarea constructivă a tuturor legilor logice posibile sub forma unor afirmații identice. Calculul predicatelor ne permite să construim teorii formale sub forma unui sistem de formule care sunt adevărate în interpretarea aleasă.
1.1. Calculul Thue (matematicianul norvegian Thue în 1912 a formulat cel mai general model de calcul)
unde este alfabetul finit
- reguli de substituție, unde (- cuvinte din alfabetul A). A * sunt toate cuvintele din alfabetul A; regulile "funcționează" în ambele direcții.
IT permite rezolvarea în mod constructiv a două probleme de bază - problema generării și sarcina de recunoaștere a cuvintelor care fac parte din IT.
a) Sarcina de a genera cuvinte echivalente în IT.
Cu un cuvânt, generați toate cuvintele posibile W. Rezultatul de la Z prin regulile lui P din IT. Setul de cuvinte deductibile de la Z. se numește clasa de echivalență în raport cu Z. și toate cele ale lui, se spune că sunt echivalente ( W).
b) Problema recunoașterii echivalenței unei perechi de cuvinte.
ZâșW (echivalent) dacă cuvântul W derivă din Z prin regulile lui P.
Ordinea de aplicare a regulilor de rezolvare a problemelor nu este reglementată și se efectuează în conformitate cu arborele căutării complete.
Exemplul 1., unde este un set gol. Cuvântul este un șir Markov.
Cuvântul "aba" din acest IT este derivat în mai multe moduri (secvențe de aplicare a regulilor).
1.2. Calculul lui Herbrand-Godel. (IUE)
In 1934, Herbrand și nu independent de ea ca Godel clarifica conceptul de algoritm pentru a construi un calcul formal de a calcula toate funcțiile posibile pe set de numere naturale.
b) PPF sunt formule bine formate care constau din termeni construiți conform regulilor acceptate în matematică și având forma -, unde u sunt termeni.
- Înlocuirea unui semn numeric în locul numelui variabil
- înlocuirea (înlocuirea) termenului cu o cifră (număr).
Exemplul 2. Este definit un sistem PPF.
Calculați funcția pentru valori
Dacă sistemul este definit ca o operație de adăugare
apoi prin regulă.
Algoritmul sub forma calculului Erbran-Gödel nu determină ordinea de aplicare a regulilor de substituție și nici nu definește o schemă de permutare, așa cum se obișnuiește în funcțiile Kleene recursive. Ca și în orice definiție a conceptului algoritmului (MT, USM, RF), formalismul IUE este construit doar pe transformările unei secvențe de simboluri și nu necesită nici o semantică.
2. Sistemele formale (FS)
Un sistem formal este un calcul în care se alocă un subset de formule (cuvinte), care este declarat inițial deductibil. Aceste formule sunt numite axiome.
a) PPF sunt formule bine formate în alfabetul A,
b); A * este setul de cuvinte construite în alfabetul A.
c) - axiomele sunt un subset al PPF.
d) regulile PV ale speciei, ceea ce înseamnă că PPF derivă din setul de PPF. În orice FS, o multitudine de formule PFTA sunt extrase din PPP utilizând regulile PI. În acest caz, PPPF> PPF>, - se numesc formule derivabile.
De exemplu, calculul propozițional este un sistem formal în care formula PPF sunt construite din nume de variabile, operații semne ( - conjuncție, - disjuncție, - negație, - implicare) și paranteze. Se individualizează PPF, care sunt axiome declarate și singura regulă de ieșire este "modus ponens". În calculul propozițional, numai astfel de PPF-uri sunt generate. care pot fi interpretate ca formule identice (tautologii) și numai ele.
3. Gramatici formale (FG)
Calculul sub formă de FS a fost propus de matematicianul american Chomsky (1953) pentru a rezolva mai întâi problemele lingvisticii structurale, apoi descrierea limbajelor oficiale de programare.
FG =. unde A este un alfabet terminal
- alfabetul auxiliar, S - singura axiomă, P - regulile formei și, unde.
FG generează o limbă caracteristică sub forma unui subset de cuvinte. Regulile FH nu conțin restricții privind recursivitatea substituțiilor.
4. Automate și gramatici
a) Alfabetul final este alfabetul terminal (mici litere latine).
b) - toate cuvintele obținute din literele alfabetului; - operația de iterare a atribuire (concatenare). De exemplu, cuvântul = aabcc este derivat din "a" prin atribuirea literei "a" literei "a" - atunci se obține prin atribuirea succesivă a literelor cuvântului .
c) - o limbă, în general, constă dintr-un număr infinit de cuvinte. Există problema descrierii limbajului cu ajutorul unor obiecte finite și constructive (de exemplu, formule sau reguli de generare).
Ca de obicei, sunt luate în considerare două sarcini principale.
d) Generarea de limbi străine. Pentru generarea cuvântului este o construcție specială - gramatica generatoare G. care este un set finit de produse (reguli de permutare) pentru derivarea oricărui cuvânt de limbă de la simbolul special S (axiome) și numai de ele.
A - alfabet de bază, V - alfabet auxiliar, - axiom
- alfabet combinat, reguli P (substituții, produse): are forma, unde (în cazul general) (cuvintele din alfabetul combinat)
e) Recunoașterea cuvintelor limbii. Având în vedere cuvântul , determinați sau. Pentru a rezolva această problemă, recunoașteți automatele. Formal, automatul este definit -, unde A este alfabetul de bază, S este alfabetul de stat, P este regulile formei, si. wi Sj. .
4.1. Automat (regulat) gramatică-AH și
mașină de stat finită.
Gramatica automată, unde A este alfabetul principal; P - regulile formei - axiomă. Un automat finit, unde A este alfabetul de bază; S - alfabetul statelor; s0 este starea inițială; sk este starea finală; P sunt regulile formularului
Exemplul 3. Pentru limba L1 sunt date:
stat
- token de sfârșit de cuvânt
Regulile AG pentru generarea de reguli de tranziție în CA
AH generează cuvintele limbajului L1 Nava spațială recunoaște cuvintele limbii L1.
Dacă sunt date regulile AH, regulile KA sunt obținute prin despărțirea formală a simbolurilor A de la partea dreaptă a regulilor la cea stângă (vezi exemplul). Dacă sunt date regulile navei spațiale, atunci regulile AH poartă simbolurile A în partea dreaptă a regulilor.
SC este specificat de graficul de tranziție și este în esență o mașină de stat (SM).
În plus, limbajul automatului este specificat printr-o expresie regulată (o formulă cu literele A, semne de operare: "-" - concatenare "," iterație "," separat "sau"). De exemplu, expresia regulată pentru L1 = ().
Exemplul 4. Să L2 limba în figura dată graficul al cuvântului, spun ei, care este recunoscut de către CS, dacă sunteți în acțiunea ajunge la .Slovo CA nu este recunoscut; Nava spațială de la S0 rămâne în S1 sub acțiunea lui w2. deoarece Nu există nicio regulă care să deducă din S1 sub acțiunea oricărui simbol, cu excepția "b" și "".
O expresie regulată pentru o limbă ale cărei cuvinte sunt recunoscute de CS.
Exemplul 5. Derivarea unui cuvânt în AG din exemplul 3.
Rezultatul cuvântului aaacbbb. În cercuri sunt numerele de reguli.
4.2. Teoremele lui Kleene. (direct și invers)
a) Prin expresie regulată, poate fi construită o navă spațială
b) Pe SC poate fi construită o expresie regulată
Formal, orice mașină de stat este un automat finit și, prin urmare, teorema Kleene se extinde la SM.
5. Gramatici fără contexte și stocare
Mașini. Limbi fără limbaj.
Există limbi care nu pot fi descrise de o expresie regulată și, în consecință, nu se poate construi o navă spațială care să recunoască cuvintele acestei limbi.
Un exemplu de astfel de limbă, în care ... Numărul a și b în cuvântul L3 este același, de exemplu, un cuvânt și un cuvânt.
Context free grammar (CSG).
A - alfabetul limbii (alfabet terminal) =; V - alfabet auxiliar =, unde - simbolul inițial - axiom ("început"); - alfabetul combinat P - regulile formei, unde - un cuvânt din literele alfabetului combinat.
Exemplul 6. Gramatica generatoare pentru
Reguli de generare (substituții, produse)
1. Rezultatul cuvântului aaacbbb
Spre deosebire de gramatica gramatica din exemplul 3, care generează cuvinte, inclusiv, KCG din exemplul 6 generează cuvinte cu un număr egal de "a" și "b" și numai cu ele.
Limbile generate de gramatici CS sunt numite limbi fără limite de context.
Documente conexe:
Seturi și expresii regulate, automate finite. Curs 12 Gramatiști și recunoscători ai lanțului de ieșire. iar R este definit într-un sistem formal. de exemplu, în algebra cantităților, algebra seturilor, în calculul propozițiilor etc., de exemplu.
Principiul programării logice. Sisteme formale (axiomatice). Conceptul de sistem formal. inferență formală. Calculul afirmațiilor ca sistem formal. Teorema deducției.
lingvistică, în special așa-numitele gramatici de transformare. dezvoltat de N. Chomsky. În prezent. formale. Rezultatele dezvoltării disciplinelor de științe naturale (cum ar fi diferențialul, calculul integrat).
logica formală este condiționată și depinde de acord? Și nu aici. Deși în interiorul logicii calculului. gramatica nu funcționează cu un cuvânt, ci cu vocabular. Între anii 1934 și 93b ani V. în cursul prelegerilor. diviziv, că automatele și sistemele fiziologice pot fi acoperite.
educație: gimnastică, gramatică. muzică și muzică. Lucrarea sa "Prelegeri despre industrie. declarații elementare ale calculului propozițional ". sistem formal. este emis în alt sistem. mai mult. Crearea de mașini automate de producție. efectuarea de bază.
Articole similare
Trimiteți-le prietenilor: