border=0

Formale grammatika

It algoritme waard earder definiearre as in alfabetyske operateur mei in finite systeem fan transformaasjeregels. Om input, intermediate and output words te skriuwen, brûk dan in alfabetysk. Eftich moatte de transformaasje regels beskreaun wurde. Fansels freget dit in pear taal. Is de gewoane sprutsen taal gaadlik foar de beskriuwing fan 'e algoritme?

Elke natuerlike taal ûntstie as in middel fan kommunikaasje tusken minsken. It is dêrom dat soksoarte funksjes hat lykas:

Variabiliteit, dy't bestiet yn 'e ymmigraasje fan' e wurdskat fan 'e taal;

Ambiguity yn 'e ynterpretaasje fan útspraak fan ferskate minsken;

Redundancy, sa't yn 'e haadstik "Kodearring fan symboalyske ynformaasje" besprutsen is.

Dizze funksjes jouwe it gebrûk fan 'e natuerkunde net it algoritme skriuwe, om't ien fan' e eigenskippen fan 'e algoritme syn determinisme is, d. Unôfhinklikens fan 'e stappen troch ien útfierd. De ienfâldichste manier om de ûnwillekeare eigenskippen fan natuerlike talen te oerwinnen is de bou fan keunstmjittige talen mei string syntaksis en komplete semantyske definityf - soksoarte talen wurde formele neamd .

Yn elke taal, natuerlik of keunstmjittich, kinne twa komponinten ûnderskiede: syntaksis en semantika. Syntaksis (grammatika fan in taal) is in set fan regels neffens hokker konstruksjes akseptabel binne yn in bepaalde taal binne boud. Semantika - de semantyske kant fan 'e taal - it relatearret de ienheden en konstruksjes fan' e taal mei guon bûtenwrâld, om te beskriuwen hokker taal brûkt wurdt.

Om in formele taal te beskriuwen, wurdt in oare taal nedich, mei help fan hokker taalkonstruksjes wurde makke. De beskreaune formele taal wurdt in objektive taal neamd, en de taal dêr't de beskriuwing makke wurdt is in metaalwurd. De meta>

Elke grammatika begjint mei in yndikaasje fan it alfabet, d. karakter setten troch hokker taalkonstruksjes boud wurde.

De syntaksis fan in formele taal is definiearre troch in bepaalde regelingssysteem (it generearjende systeem), dy't, fan in lyts set fan begjin-bouwurken, alle tastien kombinaasjes fan har generearret, d. In taal wurdt foarmen as in set fan kombinaasjes fan boarnefoarmingen dy't troch regels tastien binne. Fierder befettet de syntaksis in ferklearring fan 'e kondysje, dy't útfiert wurdt foar folsleine taalkonstruksjes en wurdt net oarspronklik útfierd.

Neist de syntaksis is in regelsystem fêststeld dat taalkonstruksjes betsjutte kin, dat regels foarmje de semantika fan 'e taal.

Formale grammatika is in systeem fan regels dy't beskriuwt in opset fan finite seksearen fan formele alfabetpersoanen.

De finite keamers fan tekens binne sellen neamd fan in formele taal, en de opset fan ketten sels is de taal dy't beskreaun is troch dizze grammatika.

De set fan syntaksisregels fan in formele taal is fergelykber mei it permutearingssysteem dat brûkt wurdt yn normale Markov-algoritmen. De konklúzje yn dizze generatyske grammatika is in syklus fan keamers, wêryn't elk, begjinnend mei de twadde, fan 'e eardere tapassing fan elke ynfolger regel krije.

In formele grammatika wurdt jûn troch in bestelde kwadrûze { T , N, S, P } , wêrby't T en N ferskillende definitive sets binne dy't in alfabet of wurdboek fan in formele taal generearje; T wurdt de set (wurdboek) fan terminalsymbols neamd; N - in set (wurdboek) fan non-terminal (assistint) tekens. S is it earste (selektearre) helpsymboal fan 'e set N. P is in set fan regels foar it oplieden fan taalkonstruksjes (substitúsjes) fan it selektearre helpsymboal, mei de foarm gh, wêrby g en h binne ketten besteande út beide terminal en net-terminalsymboalen.

De substitúsjes wurkje sa: As de string yn 'e snaar ferfoarme is g , dan wurdt it ferfongen troch it wurd h. De iennige beheining fan 'e type of substitúsjes is dat it wurd g net allinich bestiet út terminal tekens. Dit betsjut dat op in bepaalde stap in ketting dy't allinich fan terminal-symboalen befettet, jout oan de ôfsluting fan it generaasjeproses - dizze ketting is de krekte, folsleine bou fan de generearre taal. De substitúsjes P kinne oanwend wurde yn 'e ferfoarlikbere keatling yn elke folchoarder.





Sjoch ek:

Organisaasje fan datastrukturen yn RAM

Ynformaasje en alfabet

Foarbyld 7.9

Concept of model

Diskrete ûngedienste apparaten

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info