Know Intuit, prelegerea, descrierea gramatici formale

Așa că am ajuns la punctul principal al prezentării materialului desigur - descrierea așa-numita gramatica formală. Importanța gramatici formale în prelucrarea datelor cu caracter, toate în informatică este comparabilă cu importanța aritmetică în matematică, logică, filosofie etc. Pe principiile gramaticii formale și sunt concepute pentru a crea noi limbaje de programare, programe sunt scrise de ortografie și stil, programate interfețe de „exprimare“, a crea un program de corectare a erorilor și „optimizare“ de implementare a programului. Bazat pe gramatica formală a reușit să „decodifice“ armonia în capodopere ale marilor arhitecți, artiști și compozitori. (Apropo, cele mai multe fugile lui Bach scrise într-un mod care dă naștere la ei este una dintre gramatici)!

Concluziile teoriei gramaticile formale sunt utilizate în limbaje de programare logice (de exemplu, Prolog) pentru construirea de arbori de derivare.

Când citiți această secțiune, poate fi necesar să se facă referire atât anterior și secțiunile următoare. Mai detaliat în această secțiune materialul este prezentat în [41].

10.1. alfabet

Învățarea orice limbă persoana care începe cu alfabetul. Gramatica formală a unei limbi este determinată, indiferent de sensul său. Mai mult decât atât, una și aceeași limbă poate fi configurat în mai multe gramatici! E ca în școală - nu ca rezultat important (care poate fi citit la sfârșitul tutorial) cum să-l primească - înregistrate într-o soluție de notebook-uri. Prin urmare, am ajuns la determinarea alfabetului ca o formalitate.

O p e n d e n e Alfabetul -. Este un set finit nevid de elemente.

Alfabetul limbii „clasice“ - un set de caractere. În fonetică - un set de discurs uman publicat sunete. Muzica - un set de memo-uri, etc.

Cu ajutorul alfabetului este adesea posibil pentru a descrie un număr infinit de cuvinte. Setul de toate cuvintele care pot fi create de gramatica (cu alte cuvinte, gramatica generativă) se numește limbaj. Spre deosebire de limba alfabetului poate fi infinit.

Fiecare secvență finită de simboluri ale alfabetului este numit un cuvânt, sau un lanț mai profesional. Lanțuri compuse din simbolurile vor avea următoarea secvență: a, b, c, aa, ab, bc, ac. bb, ABBA, și altele. De asemenea, admite existența șir gol L - o lipsă totală de caracter. De asemenea, important este ordinea personajelor într-un șir de caractere. Astfel, lanțul ab și ba - lanțurile diferite. Următoarele litere majuscule vor fi folosite ca variabile și simboluri și litere mici vor desemna lanțuri. De exemplu:

lanț alcătuit din caractere și T. S. V și în această ordine.

O p e n d e n e. Lungimea catenei nu este numărul de caractere din acest lanț. Acesta este denumit | x |. De exemplu: | A | = 0, | A | = 1, | BA | = 2, | ABBA | = 4.

Dacă x și y sunt siruri de caractere, acestea vor fi concatenarea xy șir. Prin lanțuri permutare, ca urmare a concatenarea se schimbă (ca în teoria grupurilor). Dacă z = xy - string, apoi x - cap, și y - lanț coadă. Dacă ne pasă de capul lanțului, vom nota:

și dacă suntem indiferenți la coada, vom scrie:

Dacă limba este infinit, atunci ea determină gramatica trebuie să fie recursiv.

Notă privind recurență stânga-verso. Unii algoritmi care implementează concluzia inversă, în timp ce recursivitatii stânga față pot intra în „buclă infinită.“ De exemplu, în gramatica în [Exemplul 01] a treia regulă poate fi executată la infinit: atunci când este accesată regula: <чс>. = <чс><цифра> - programul va „să acorde o atenție“, simbolul <чс> și „ignorați“ simbolul <цифра>. Acest lucru poate fi corectat o selecție de gramatică. astfel încât ordinea de selecție a regulilor și faptelor. de fapt, o regulă recursiv - De exemplu, în Prolog prima regulă care se produce o oprire recursivitatii, și numai apoi în scris.

Notă. Aici există unele „deconectare“, cu aprobarea [paragraful 3 al „Gramatica“], care prevede că rezultatul de ieșire nu depinde de ordinea regulilor. Cu toate acestea, soluția problemei (rezultatul algoritmului) nu depinde de ordinea regulilor - determină numai dacă va exista o decizie emisă de un număr finit de pași în cazul în care programul este completat în mod normal, sau sistemul va eșua. Acest lucru - nu este o lipsă de gramatică. și lipsa unui algoritm, care a fost generat.