I det generelle tilfellet er et språk et uendelig sett, og uendelige objekter er til og med vanskelige å definere: de kan ikke defineres ved bare å liste elementene. Enhver endelig mekanisme for å spesifisere et språk kalles en grammatikk.
Et formelt språk er et sett med strenger i et begrenset alfabet. Formelle språk inkluderer kunstige språk for menneske-maskin-kommunikasjon - programmeringsspråk.
For å spesifisere en beskrivelse av et formelt språk, er det for det første nødvendig å spesifisere alfabetet, det vil si et sett med objekter kalt symboler (eller bokstaver), som hver kan reproduseres i et ubegrenset antall kopier (som vanlige trykte bokstaver) eller tall), og for det andre for å definere en formell grammatikk for språket, dvs. liste reglene som symboler brukes til for å konstruere sekvenser som tilhører språket som defineres - vanlige kjeder.
Reglene for formell grammatikk kan betraktes som produkter (inferensregler), det vil si elementære operasjoner som, når de brukes i en bestemt sekvens på den opprinnelige kjeden (aksiom), bare genererer korrekte kjeder. Selve sekvensen av regler som brukes i prosessen med å generere en viss kjede er konklusjonen. Språk definert på denne måten er et formelt system.
I henhold til metoden for å spesifisere riktige kjeder, er formelle grammatikker delt inn i generative og gjenkjennende. Generative grammatikker inkluderer grammatikkene til språket L,
hvorfra det er mulig å konstruere hvilken som helst "riktig" kjede som indikerer dens struktur, og det er umulig å konstruere en enkelt feil kjede. En gjenkjennelsesgrammatikk for et språk L er en grammatikk som lar en bestemme om en vilkårlig valgt streng er korrekt og, hvis den er riktig, deretter å bestemme strukturen. Gjenkjennelsesgrammatikken setter kriteriet for at en vilkårlig streng skal tilhøre et gitt språk.
Formelle grammatikker er mye brukt i lingvistikk og programmering.
kunnskap i forbindelse med studiet av naturlige språk og programmeringsspråk.
Automatiske og språklige modeller er bygget på grunnlag av teorien om formelle grammatikker, hvis grunnlag ble lagt i verkene til N. Chomsky. Hovedobjektene som denne teorien omhandler er symboler, som er de grunnleggende elementene i ethvert ikke-tomt sett A av enhver art, samt kjeder konstruert fra disse elementene. Mengden A kalles også alfabetet.
Vi vil betegne symboler med små bokstaver i det latinske alfabetet, og kjeder – i formen ffghhh, som vi vil vurdere orientert fra venstre til høyre. Vi vil også betegne kjeder med spesielle symboler - store bokstaver i det latinske alfabetet eller greske bokstaver, for eksempel: = ffg, B = abba. La oss introdusere en tom kjede som ikke inneholder et enkelt tegn.
Lengden på en kjede vil være antall tegn som er inkludert i denne kjeden.
Lengden på kjeden er angitt som følger:
| | = | ffg | = 3;
| B | = | abba| = 4;
Sammenkoblingen av to kjeder X og Y er en kjede Z som oppnås ved direkte å slå sammen kjeden X til venstre og kjeden Y til høyre. For eksempel, hvis X = ffg, Y = ghh, så er sammenkoblingen av X og Y kjeden Z = ffgghh. La oss betegne sammenkoblingsoperasjonen med symbolet o. Egenskaper til denne operasjonen
kan skrives som følger:
1) stengingsegenskap:
o: A* × A* → A*;
2) egenskap ved assosiativitet:
(∀X ∈ A*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
hvor A* betegner settet av alle mulige kjeder (uendelig, selvfølgelig), sammensatt av en endelig sett A av grunnleggende elementer (symboler) i ordboken, inkludert den tomme kjeden ; symbolet x angir driften av det kartesiske produktet av to sett; og X, Y, Z er vilkårlige kjeder som tilhører A*.
Tenk på paret (A*, 0). Med tanke på de listede egenskapene til operasjonen o, er dette paret en semigruppe med identitetselementet eller en monoid. I algebra kalles bare et sett (i dette tilfellet A*) utstyrt med en definert assosiativ operasjon en semigruppe.
En streng hører kanskje til språket L eller ikke. Ethvert sett med strenger L ≤ A* (der A* er en monoid) kalles et formelt språk hvis dette settet med strenger er definert i alfabetet A.
Eksempel 1. La A være et sett med bokstaver i det russiske alfabetet. Da representerer settet med strenger sammensatt av fem bokstaver det formelle språket L1. Et annet eksempel på et språk definert i det samme alfabetet er settet med L2 på fem bokstaver
ord i det russiske språket som finnes i en staveordbok. Au-
man kan se L2 ⊂ L1, siden mange strenger i L1-språket ikke er russiske ord.
La B og C være noen delmengder av mengden A*.
Produktet av sett B og C er settet D av kjeder, som er
bestående av sammenkobling av kjeder av B og C, dvs.
D = (X o Y | X ∈ B, Y ∈ C).
Produktet er betegnet som følger: D = BC.
Tenk på alfabetet A. La oss betegne mengden som består av med A0. Definere
del graden av alfabetet som Аn = An-1 A for hver n ≥ 1.
Det er ikke vanskelig å vise at settet med alle mulige kjeder av alfabetet
Et slikt sett kalles en iterasjon av alfabetet A. En avkortet iterasjon av alfabetet
Favita A kalles
Hvis X og Y er kjeder av settet A*, kalles kjeden X en underkjede av kjeden
knopper Y, når det er kjeder U og V fra A* slik at
Dessuten, hvis U er en tom kjede, kalles underkjeden X kjedens hode
ki Y, og hvis V er en tom kjede, kalles X halen til kjeden Y.
Sammenkoblingen av to strenger X og Y er betegnet XY eller XY. Tenk på par av kjeder (P1, Q1), (P2, Q2), ..., (Pn, Qn) fra A* x A*. Thues forhold vil være reglene som enhver verdi
en knopp X = U Pi V fra settet A* vil bli assosiert med en kjede Y = U Qi V fra samme sett A* (i = 1, 2, ..., n) og vice versa. Disse relasjonene fører til den såkalte assosiative kalkulus.
Hvis kjeden Y er oppnådd fra kjeden X ved en enkelt anvendelse av en Thue-relasjon (dvs. å erstatte underkjeden Pi med underkjeden Qi), vil vi si at X og Y er tilstøtende kjeder.
Kjeden Xn er korrelert med kjeden X0 hvis det er en sekvens av kjeder
X0, X1, ..., Xn,
slik at Xi-1 og Xi er tilstøtende kjeder.
Eksempel 2. La A være settet med bokstaver i det russiske alfabetet som
lim Thues forhold, som består i retten til å erstatte en hvilken som helst bokstav i et ord med en hvilken som helst annen. Deretter i sekvensen av kjeder MEL, MUSE, LUZA, VINE, POSE, TID, PORT, KAKE, er to tilstøtende kjeder tilstøtende, og kjedene MEL og KAKE er korrelert i betydningen de gitte relasjonene.
Innføringen av Thues relasjoner gjør det mulig å identifisere visse klasser av språk blant mange språk, som brukes i konstruksjonen av automatiske språklige modeller av forskjellige typer.
Thues relasjoner er tosidige hvis kjeden X er ved siden av kjeden Y, og omvendt, kjeden Y er ved siden av
kjede X. Mer interessant, fra synspunkt av teorien om formell grammatikk, er
Det er sammenhenger i hvilken retning introduseres.
I dette tilfellet kalles de Thue semi-relasjoner eller produkter og beskrivelser.
betyr som følger:
(P1 → Q1), (P2 →Q2), ..., (Pn → Qn).
I tilfellet der det er et sett med produkter, sier vi at kjeden Y er ufullstendig.
genereres direkte fra kjeden X, og er betegnet som X ⇒ Y hvis det finnes kjeder U og V slik at
X = U Pi V, Y = U Qi V,
og (Pi → Qi) – produkter fra dette settet.
Det sies også at X avler Y.
Hvis det er en sekvens av kjeder X0, X1, ..., Xn slik at for hver
før i = 1, 2, ..., n
X i-1 ⇒ X i,
så sier de at Xn er generert fra X0 (X0 genererer Xn), og betegner det som X0 ⇒ * Xn. .
Chomskyan grammatikk tilsvarer formelle kombinatoriske skjemaer,
som er Thue-semi-systemer basert på Thue-semi-relasjoner
Merknad: Denne delen diskuterer det grunnleggende i disiplinen: "formell grammatikk". Denne disiplinen vurderer alle operasjoner med symboler, og konklusjonene er mye brukt i analysen av formelle og "menneskelige" språk, så vel som i kunstig intelligens. Denne forelesningen er den viktigste og samtidig den vanskeligste forelesningen å forstå i kurset. I denne forbindelse presenterer forfatteren leseren kun med konklusjonene sine, og utelater de matematiske bevisene. For bedre å forstå materialet, må du kanskje referere til tidligere og etterfølgende forelesninger.
10.1. Alfabet
En person begynner å lære et hvilket som helst språk med alfabetet. I formell grammatikk språk er definert uavhengig av betydningen. Dessuten kan det samme språket dannes av flere grammatikker! Det er som på skolen - resultatet (som kan leses på slutten av læreboken) er ikke like viktig som kvitteringen - løsningen på problemet registrert i notatboken. La oss derfor nærme oss definisjonen av alfabetet også formelt.
Definisjon. Et alfabet er et ikke-tomt begrenset sett med elementer.
I et "klassisk" språk er alfabetet et sett med bokstaver. I fonetikk, et sett med talelyder laget av mennesker. I musikk er dette et sett med noter osv.
Ved hjelp av alfabetet er det ofte mulig å beskrive uendelig sett ord Settet med alle ord som kan lages ved hjelp av grammatikk (med andre ord generert av grammatikk) kalles et språk. I motsetning til alfabetet kan språket være uendelig.
Noen endelig sekvens alfabetet tegn kalt et ord, eller, mer profesjonelt, en kjede. Kjeder som består av tegn (a, b, c) vil være følgende sekvenser: a, b, c, aa, ab, bc, ac, bb, abba og andre. Eksistensen av en tom kjede A er også tillatt - et fullstendig fravær av symboler. Rekkefølgen på karakterene i kjeden er også viktig. Så kjedene ab og ba er forskjellige kjeder. Videre vil store latinske bokstaver brukes som variabler og symboler, og små latinske bokstaver vil betegne kjeder. For eksempel:
X = SVT-oppføring 10.1.
en streng som består av tegnene S, V og T, og i den rekkefølgen.
Definisjon. Lengden på en kjede er antall tegn i denne kjeden. Det er betegnet som |x| . For eksempel: |L| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.
Hvis x og y er strenger, vil sammenkoblingen deres være strengen xy. Omorganisering av kjedene under sammenkobling endrer resultatet (som i gruppeteori). Hvis z = xy er en kjede, så er x hodet og y er halen på kjeden. Hvis vi ikke bryr oss om lederen av kjeden, vil vi betegne:
Z = … x Oppføring 10.2.
og hvis vi ikke bryr oss om halen, vil vi skrive:
Z = x ...Oppføring 10.3.
Definisjon. Produktet av to sett med kjeder er definert som sammenkoblingen av alle kjeder som inngår i disse settene. For eksempel, hvis sett A = (a, b) og B = (c,d), så:
AB = (ac, ad, bc, bd) Oppføring 10.4.
I produktet av sett, som i sammenkobling, er rekkefølgen av faktorene viktig.
Både når du sammenkobler kjeder og når du multipliserer sett med kjeder, forblir den assosiative loven sann, skrevet som:
Z = (ab)c = a(bc) = abc Oppføring 10.5.
D = (AB)C = A(BC) = ABC-oppføring 10.6.
Og til slutt bestemmer vi graden av kjeden. Hvis x er en ikke-tom kjede, da x 0 = (L), x 1 = x, x 2 = xx, x n = x(x) (n-1). Det samme gjelder graden av sett.
10.2. Terminal- og ikke-terminalsymboler
Konseptet med terminal og ikke-terminale symboler er nært knyttet til begrepet substitusjons- (eller produksjons-) regel. La oss definere det.
Definisjon. En produksjon, eller substitusjonsregel, er et ordnet par (U, x), skrevet som:
U::= x Oppføring 10.7.
hvor U er et symbol og x er en ikke-tom finitt tegnstreng.
Karakterer som bare vises på høyre side kalles terminaltegn. Symboler som finnes på både venstre og høyre side av reglene kalles ikke-terminale symboler, eller syntaktiske språkenheter. En haug med ikke-terminale symboler betegnet som VN, og terminaltegn- VT.
Merk. Denne definisjonen av terminal og ikke-terminale symboler sant for KS-grammatikk og A-grammatikk (se avsnitt 10.4.3).
Definisjon. En grammatikk G[Z] er et begrenset, ikke-tomt sett med regler som inneholder ikke-terminal symbol Z minst én gang på et sett med regler. Z-tegnet kalles starttegnet. Neste vi alle ikke-terminale symboler vi vil betegne det som<символ>.
[Eksempel 01]
Grammatikk: "tall"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
La oss gi en annen definisjon:
Definisjon. Kjeden v genererer direkte kjeden w hvis:
V=x y og w = xuy Oppføring 10.8.
Hvor ::= u er en grammatikkregel. Dette er betegnet som v => w. Vi sier også at w er direkte deduserbar fra v. I dette tilfellet kan kjedene x og y være tomme.
Definisjon. Vi sier at v genererer w, eller w reduseres til v, hvis det er en endelig kjede av utganger u0, u1, …, u[n] (n > 0) slik at
V = u0 => u1 => u2 => ... => u[n] = w Oppføring 10.9.
Denne sekvensen kalles en pinne med lengde n, og er betegnet med v =>+ w. Og til slutt skriver de:
V =>* w hvis v => w eller v =>+ w Oppføring 10.10.
10.3. Fraser
Definisjon. La G[Z] være en grammatikk, x en streng. Da kalles x en setningsform if
Definisjon. La G[Z] være en grammatikk. Og la w = xuy være en setningsform. Da kalles u en frase av setningsformen w for ikke-terminal symbol , Hvis:
Z =>* x y og =>+ u Oppføring 10.11.
Z =>* x y og => u Oppføring 10.12.
da kalles strengen u en enkel frase.
Du må være forsiktig med begrepet "frase". Det faktum at =>+ u (kjeden u kan utledes fra ) betyr ikke at u er en setning av setningsformen x y; er også nødvendig kjede fradragbarhet x y fra det innledende symbolet til grammatikken Z.
For å illustrere setningen, vurder [Eksempel 01] setningsformen<чс>1 . Betyr dette at symbolet<чс>er en setning hvis det er en regel:<число> ::= <чс>? Selvfølgelig ikke, siden kjetting ikke er mulig:<число><1>- fra det første tegnet:<число>. Hva er setninger av setningsform?<чс>1 ? Tenk på utgangen:
<число> => <чс> => <чс><цифра> => <чс><1>Notering 10.13.
Dermed,
<число> =>* <чс>Og<чс> =>+ <чс>1 oppføring 10.14.
La oss vurdere en formell grammatikk, som til en viss grad ligner et fragment av russisk grammatikk og spesifiserer et formelt språk som består av fire russiske setninger. Denne formelle grammatikken bruker elementer som fungerer som setningsmedlemmer eller deler av tale:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Disse elementene er omsluttet av vinkelparenteser for å skille dem fra de faktiske vokabularordene som utgjør setningene i språket. I vårt eksempel består ordboken av følgende fem ord, eller "tegn": V= (hus, eik, obskur, gammel, (prikk)). Grammatikk har visse regler som inneholder informasjon om hvordan setninger i et språk kan konstrueres ved hjelp av disse symbolene. En av disse reglene er:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Denne regelen tolkes som følger: "En setning kan bestå av et subjekt, etterfulgt av et predikat, deretter et objekt og et punktum." Det kan godt være andre regler i grammatikken som definerer setninger med en annen struktur. Imidlertid er det ingen slike regler i denne grammatikken. Resten av reglene er:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® tilslører
5. <прилагательное>® gammel
6. <существительное>® hjem
7. <существительное>® eik
La oss bruke denne grammatikken for å generere (eller skrive ut) en setning.
I følge regel 1 ser setningen slik ut:
<предложение>1®<underlagt e><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><addisjon> 3 →
3 →<adjektiv e><существительное> <сказуемое> <прилагательное> <существительное> 4 → Gammel <существительное> <сказуемое> <adjektiv e><существительное>
4 →Gammel <существительное > <сказуемое> gammel <существительное >
6.7 →Gamle hus <сказуемое> en gammel eik
4 → Det gamle huset er skjult av det gamle eiketreet
Dermed får vi et ferdig forslag:
Et gammelt hus er skjult av et gammelt eiketre.
Denne konklusjonen kan visualiseres som et tre. Utdatatreet viser hvilke regler som ble brukt på de ulike mellomelementene, men skjuler rekkefølgen de ble brukt i. Dermed kan det sees at den resulterende kjeden ikke avhenger av rekkefølgen som erstatningene av mellomelementer ble gjort i. De sier at treet er "syntaktisk struktur" tilbud.
Ideen om slutning viser andre tolkninger av regler som ligner på regelen <подлежащее> ® <прилагательное> <существительное> . I stedet for å si " Emne Dette adjektiv, etterfulgt av substantiv", kan vi si det Emne"gir opphav til" (eller "er avledet fra det", eller "kan erstattes av")<adjektiv><существительное>.
Ved å bruke grammatikken ovenfor kan tre andre setninger også utledes, nemlig:
Et gammelt eiketre skjuler det gamle huset.
Det gamle huset skjuler det gamle huset.
En gammel eik skjuler en gammel eik.
Disse setningene og setningen avledet tidligere er alle setningene som er generert av denne grammatikken.
Settet som består av disse fire setningene kalles et språk, som er definert av en gitt grammatikk ("generert av det" eller "avledet i det").
Et av de formelle systemene er substitusjonssystemet eller Thue-semi-systemet (oppkalt etter den norske matematikeren Axel Thue), definert av alfabetet A og et begrenset sett med substitusjoner av formen:
der α i,β i er ord, muligens tomme i A, Þ er et substitusjonssymbol, tidligere forstått av oss som "antyder", "utledet".
Thue-systemet bruker relasjoner av formen:
forstått som par av erstatninger:
α i Þ β i (venstre);
β i Üα i (høyre).
I Thue-semisystemet tolkes substitusjonen α i Þβ i som inferensregelen R i . Ved å bruke disse semisystemene dannet og utviklet den amerikanske matematikeren N. Chomsky på 50-tallet teorien om såkalte formelle grammatikker, som er deres spesialtilfelle.
La V være et ikke-tomt sett med symboler - et alfabet (eller ordbok) og dermed gitt settet V * av alle endelige ord i alfabetet V. Det formelle språket L i alfabetet V er en vilkårlig delmengde av V * . Så hvis V inneholder bokstaver i det russiske språket, skilletegn, mellomrom, etc., så er V * et hypotetisk sett som inkluderer alle verk av stor russisk litteratur (skrevet og fremtidig).
Ord, matematiske tegn, geometriske bilder osv. kan også brukes som symboler.
Språk er spesifisert eller bestemt grammatikk– et system av regler som genererer alle kjeder av et gitt språk, og bare dem.
Formell grammatikk – formelt system, kalkulus.
Det er gjenkjennende, genererende og transformerende formelle grammatikker.
gjenkjenne, hvis den for en gitt streng bestemmer om den strengen er korrekt i betydningen av den gitte grammatikken.
Formell grammatikk kalles generativ, hvis den kan konstruere en riktig kjede.
Formell grammatikk kalles transformerende hvis den for en korrekt konstruert kjede konstruerer kartleggingen i form av en riktig kjede.
Tenk på klassen av generative formelle grammatikker.
Den generative formelle grammatikken til G er den firedoble
G=
hvor T er et endelig ikke-tomt sett av endelige terminale (hoved) symboler;
N – begrenset ikke-tomt sett med ikke-terminale (hjelpe) symboler;
P er et begrenset ikke-tomt sett med slutningsregler (produksjoner);
S er starttegnet.
T – terminalordbok – et sett med innledende symboler som kjedene generert av grammatikken er bygget fra;
N – ikke-terminal ordbok – et sett med hjelpesymboler som angir klasser av kildesymboler.
Et begrenset sett er en komplett ordbok over grammatikken G.
Inferensregelen er et begrenset ikke-tomt sett med binære relasjoner av formen φÞψ, der φ og ψ er kjeder i ordboken V, symbolet Þ er "erstatt med".
Kjeden β er direkte deduserbar fra kjeden α i grammatikken G (notasjon αβ; underskrift G utelates hvis det er tydelig hvilken grammatikk vi snakker om) hvis α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ ).
Kjeden β kan utledes fra α hvis det er en sekvens E 0 =α, E 1 , E 2 ,..., E n =β, slik at "i =0,1,...,n-1 E i => E i +1.
Denne sekvensen kalles utgangen β fra α, og n er lengden på utgangen.
Utleibarheten til β fra α er betegnet med α=> n β (hvis du trenger å spesifisere lengden på utledningen).
Språket L(G) som genereres av grammatikken G er settet med strenger i terminalordboken T avledet fra S, der S er startsymbolet som angir klassen av språklige objekter som denne grammatikken er ment for. Det innledende symbolet kalles grammatikkens mål eller dens aksiom.
Grammatikken G og G 1 er ekvivalente hvis L(G)=L(G 1).
Når man beskriver et naturlig språk i form av teorien om formell grammatikk, tolkes terminalsymboler som ord eller morfemer - de minste meningsfulle språkenhetene (røtter, suffikser, etc.), ikke-terminale symboler - som navn på ordklasser og fraser (emne, predikat, predikatgruppe, etc. .P.). En streng med tegn tolkes vanligvis som en naturlig språksetning.
Eksempel 1. La grammatikken gis som følger:
T-(a,b), N-(S,A,B), S-S,
P=(1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb).
Typiske konklusjoner av forslag:
Nummeret på inferensregelen som brukes er angitt i parentes over pilene. Utgangen avsluttes pga det er ingen regel P med venstre side lik ab.
Grafen til en slik generativ grammatikk er vist i fig. 125.
Ris. 125. Generativ grammatikkgraf
Her er a og b de siste toppunktene (terminal).
Eksempel 2. La grammatikken gis som følger:
T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Du kan skrive ut kjeden<прилежный> <студент> <выполняет> <домашнее задание>.
Det er klart at den siste slutningskjeden er endelig og representerer en naturlig språksetning. På samme måte kan du utlede kjeden<ленивый> <студент> <не выполняет> <домашнее задание>. Merk at i dette eksemplet er de ikke-terminale symbolene syntaktiske kategorier.
Utgangen kan også beskrives av det såkalte strukturtreet vist i fig. 126.
Ris. 126. Strukturelt tre for setningsutgang
Grammatikken kan også spesifiseres ved såkalte Wirth-syntaktiske diagrammer - som i Pascal-språket, som ligner svitsjekretser der en seriell forbindelse indikerer en kjede, og en parallellforbindelse indikerer varianter av kjedene - i stedet for et symbol.
Så formelle grammatikker kan være gjenkjennende, generere, transformere. I tillegg, i teorien om formelle grammatikker, er det fire typer språk generert av fire typer grammatikk. Grammatikker utmerker seg ved å legge suksessivt økende restriksjoner på regelsystemet R.
Den generelt aksepterte klassifiseringen av grammatikk og språkene de genererer er Chomsky-hierarkiet, som inneholder fire typer grammatikk.
Type 0 grammatikk er en grammatikk der det ikke legges begrensninger på reglene for slutning jÞy, hvor j og y kan være hvilke som helst strenger fra V. En slik grammatikk kan implementeres av en Turing-maskin. I dette tilfellet tilsvarer tilstanden til Turing-maskinen ikke-terminale (hjelpe-) symboler, og symbolene på båndet tilsvarer terminaler. Reglene for å generere kjeder er beskrevet av et system av kommandoer.
Skriv grammatikk 1 er en grammatikk, der alle reglene har formen aАbÞawb, der wÎТUN, A er et ikke-terminalt symbol. Kjede a og b er konteksten for reglene. De endres ikke når den brukes. Således, i type 1-grammatikker, går et enkelt terminalsymbol A inn i en ikke-tom streng w (A kan erstattes av w) bare i sammenheng med a og b. Type 1-grammatikker kalles kontekstsensitiv eller kontekstsensitiv.
Type 2 grammatikk er en grammatikk der kun regler av formen AÞa er tillatt, der aÎТUN, dvs. a er en ikke-tom kjede av V. Type 2-grammatikker kalles kontekstfri eller kontekstfri. Moderne algoritmiske språk beskrives ved hjelp av kontekstfrie grammatikker.
Skriv grammatikk 3 – har regler av formen АÞaB, eller AÞb, hvor А,ВОN; litt.
Her er A,B,a,b enkelttegn (ikke kjeder) i de tilsvarende ordbøkene. Språk som er definert av grammatikk av denne typen kalles automatisk eller vanlig.
I dette tilfellet brukes et regulært uttrykksspråk (vanlig språk) av formen:
Et slikt språk er gitt av en begrenset automat (Kleenes teorem). I de fleste algoritmiske språk spesifiseres uttrykk ved hjelp av endelige tilstandsmaskiner eller regulære uttrykk.
La oss vurdere et eksempel på å spesifisere et vanlig språk med en begrenset maskin:
X=(0,1) – sett med inngangssymboler;
Y=(S,A,B,q k ) – sett med interne tilstander, q k – slutttilstand, S – starttilstand.
Noen ganger vurderes flere slutttilstander og kombineres til et sett F. I dette tilfellet er F = (q k ).
j: overgangsfunksjon – ikke-deterministisk:
Overgangsgrafen til en endelig ikke-deterministisk automat er vist i fig. 127.
Ris. 127. Overgangsgraf for en endelig ikke-deterministisk automat
Den tilsvarende generative grammatikken er:
Tilsvarende vanlig språk L= 
:
0, 010, 01010,...
Teorien om formell grammatikk brukes i konstruksjonen av kompilatorer. Kompilatoren analyserer kildeprogrammet. Samtidig bestemmes det om en gitt kjede av tegn er en riktig konstruert setning, og i så fall gjenopprettes formen. Parsing eller syntaktisk analyse utføres av et spesielt program - en parser (for å analysere - parse). For å løse dette problemet er det utviklet spesielle programmer, for eksempel LEX og YACC.
UNIX-operativsystemet har standardprogrammene LEX og GREP - de er bygget på grunnlag av vanlig språkteori.
LEX-programmet utfører leksikalsk analyse av tekst - bryter ned tekst i samsvar med et spesifikt sett med regulære uttrykk.
GREP-program - velger et mønster ved hjelp av et regulært uttrykk - dvs. utfører et kontekstuelt søk i en eller flere filer, mens den bygger en endelig tilstandsmaskin som symboler fra inngangssymbolstrømmen mates til.
I automatiske oversettelsessystemer fra ett språk til et annet identifiseres emnet, predikatet, definisjonen og komplementet; deretter utarbeides et tilsvarende forslag i henhold til reglene for det påkrevde språket.
For tiden bruker datamaskiner oversettere som Promt, Magic Gooddy, Socrat Personal. I tillegg brukes enkle ordbøker, som .Context, Socrat Dictionary, MultiLex.
Representasjon av språklig kunnskap ved bruk av formelle grammatikker er en av modellene for kunnskapsrepresentasjon generelt, brukt på et område som systemer med elementer av kunstig intelligens. Det skal bemerkes at kunnskap skiller seg fra data, for eksempel ved at data kun tolkes meningsfullt av det tilsvarende dataprogrammet, og i kunnskap er muligheten for meningsfull tolkning alltid til stede. Programvare- og maskinvaredelen av systemer som gir et grensesnitt med brukeren på naturlig eller nær naturlig språk er implementert språklig prosessor, hvis oppgave er direkte og omvendt oversettelse av naturspråklige tekster til det formelle språket til den interne representasjonen som datamaskinen arbeider med.
I Japan har noen selskaper allerede begynt å selge husholdnings "snakende" roboter som kan kommunisere med eieren.
Den språklige prosessoren har deklarative og prosedyremessige deler. Den første inneholder en beskrivelse av ordbøker, den andre - en algoritme for analyse og syntese av naturlige språktekster.
Logiske modeller for representasjon av kunnskap er allerede kjent for oss kalkulering av proposisjoner og predikater.
Grunnlaget for formalisering av semantisk (nosjonell) kunnskap om et bestemt fagområde er de såkalte semantiske nettverkene. Et semantisk nettverk er en rettet graf, hvis toppunkter er assosiert med spesifikke objekter, og buene er assosiert med semantiske forhold mellom dem. Vertex-etiketter er referanser i naturen og representerer visse navn. Navnens rolle kan for eksempel være ord av naturlig språk. Bueetiketter angir elementer i et sett med relasjoner. I tillegg brukes rammer for å representere kunnskap, som oftest defineres som en datastruktur for å representere stereotype situasjoner.
Gödels teoremer
I matematisk logikk er det bevist at predikatregning er konsistent - d.v.s. det er umulig å vise , og samtidig. I tillegg, i kraft av Gödels teorem om fullstendigheten av predikatregning, kan en generelt gyldig formel utledes i predikatregning.
Den betraktede predikatregningen er en førsteordens predikatregning. I andreordens kalkulering er kvantifiserere etter predikater mulige, dvs. uttrykk av formen "P(P(x)), eller av funksjoner.
Så settet med alle sanne utsagn om proposisjonell logikk er tallrike og kan avgjøres. Settet med alle sanne utsagn av predikatlogikk er tallrik (på grunn av dens fullstendighet), men uavgjørelig (på grunn av uendeligheten til fagområdet).
Som en annen formell teori innen matematisk logikk, vurderes den såkalte formelle aritmetikken foreslått av den italienske matematikeren Giuseppe Peano (1858-1932). Peano introduserte symbolene og operasjonene O, U, I og var den første som presenterte logikk som en matematisk disiplin. Det første forsøket på å redusere matematikk til logikk ble gjort av den tyske matematikeren og logikeren Gottlieb Frege (1848-1925). Det var han som definerte sett som volumet av et konsept. Han skrev: "Aritmetikk er en del av logikken og bør ikke låne fra verken erfaring eller kontemplasjon noen bevisgrunnlag." Det berømte paradokset om settet av alle sett er en selvmotsigelse i Freges system identifisert av Bertrand Russell.
Gödel beviste at enhver formell teori T som inneholder formell aritmetikk er ufullstendig: den inneholder en lukket formel F slik som er sann, men verken F eller kan utledes i T. I følge Gödels berømte ufullstendighetsteorem, for enhver konsistent formell teori T som inneholder formell aritmetikk, formelen som uttrykker konsistensen til T kan ikke bevises i T.
Dermed er aritmetikk og tallteori ikke-aksimiserbare teorier, og settet med alle sanne utsagn om aritmetikk er utellelig.
Gödels teoremer har viktig metodisk betydning. Det viser seg at for tilstrekkelig rike matematiske teorier er det ingen tilstrekkelige formaliseringer. Riktignok kan enhver ufullstendig teori T utvides ved å legge til den som et aksiom en formel som er sann, men som ikke kan utledes i T, men den nye teorien vil også være ufullstendig. I tillegg er det umulig å studere metaegenskapene til en teori ved å bruke midlene til selve den formelle teorien, dvs. enhver metateori T, for å kunne bevise minst konsistens, må være rikere enn T.
Dermed settes det spørsmålstegn ved selve tilnærmingen med å konstruere matematikk som et visst fast sett med midler som kan erklæres som de eneste legitime og med deres hjelp til å bygge metateorier av noen teorier. Men dette er slett ikke sammenbruddet av den formelle tilnærmingen. Tilstedeværelsen av uløselige problemer betyr ikke at en konstruktiv tilnærming ikke er egnet hvis den ikke kan gjøre noe, er det bare fordi ingen kan gjøre det.
Umuligheten av fullstendig formalisering av substansielt definerte teorier er ikke en mangel ved konseptet, men et objektivt faktum som ikke kan elimineres av noe konsept.
Umuligheten av adekvat formalisering av en teori betyr at man enten må lete etter formaliserbare fragmenter av den, eller bygge en sterkere formell teori, som imidlertid igjen vil være ufullstendig, men kanskje vil inneholde hele den opprinnelige teorien.
IKKE-KLASSISK LOGIKK
INNLEDNING……………… ………………………………………….………………….4
Kapittel 1. SPRÅK OG GRAMMATIKK. SYMBOLER, DEFINISJONER OG KLASSIFISERING………………………………………………………………………………6
1.1. Begrepet språkgrammatikk. Betegnelser………………………………………………………………7
1.2. Klassifisering av grammatikk i henhold til Chomsky………………………..…………………13
1.3. Teknikker for å konstruere KS- og A-grammatikk…………………………………………………………………..16
1.4. Syntaktiske slutningstrær i KS-grammatikk. Opptreden
A-grammatikk i form av en tilstandsgraf. Tvetydighet i grammatikk…………………..19
1.5. Syntaktisk analyse av A-språk…………………………………………………………..23
Øvelser……………………………………………………………………………………….29
Kapittel 2. GJENKENNERE OG MASKINER.……………………………….….…………32
Kapittel 3. AUTOMATISK GRAMMATIKK OG FINITTE MASKINER…………….35
3.1. Automatiske grammatikker og endelige automater………………………………………….35
3.2.Ekvivalens av ikke-deterministiske og deterministiske A-grammatikker...... 36
Øvelser ………………………………………………………………………………………… 41
Kapittel 4. TILSVARENDE KONTEKSTFRIE TRANSFORMASJONER
OG AUTOMATISKE GRAMMATIKKER………………………………………………..….42
4.2. Eliminering av blindveisregler fra grammatikk…………………………………………46
4.3. Generaliserte KS-grammatikker og reduksjon av grammatikk til forlengende form…….48
4.4. Eliminering av venstre rekursjon og venstre faktorisering…………………………………..…52
Øvelser……………………………………………………………………………………………….53
Kapittel 5. EGENSKAPER TIL AUTOMATISKE OG KONTEKSTFRIE SPRÅK…55
5.1. Generell oversikt over kjeder av A-språk og KS-språk………………………………………………………………..55
5.2. Operasjoner på språk……………………………………………………………………….59
5.2.1. Operasjoner på CS-språk………………………………………………………………59
5.2.2. Operasjoner på A-språk………………………………………………………………62
5.2.3. Operasjoner på K-språk………………………………………………………………66
5.3. Konklusjoner for praksis………………….………………………………………………………………………….67
5.4. Tvetydighet i KS-grammatikk og språk………………………………………………………………71
Øvelser………………………………………………………………………………………………………74
Kapittel 6. SYNTAKTISK ANALYSE av CS-språk……………………………...……...75
6.1. Metoder for å analysere CS-språk. Forrangsgrammatikker………………….…75
6.2. Wirths prioritetsgrammatikker…………………………………………………………………………………77
Floyds forrangsgrammatikker…….………………………………………………………………...79
Forrangsfunksjoner………………………………………………………………81
Øvelser………………………………………………………………………………………………84
Kapittel 7. INTRODUKSJON TIL SEMANTIKK……………………………………………………….85
7.1. Polsk invers notasjon….………………………………………………………………...85
7.2. Tolkning av POLIZ………………………………………………………………..….87
7.3. Genererer kommandoer for POLIZ………………………………….………………89
7.4. Zamelson og Bauers algoritme for å oversette uttrykk til POLIZ………..……….91
7.5. Attributtgrammatikk………………………………………………………………………………………97
Øvelser………………………………………………………………………………………..100
Kapittel 8. HOVEDFASER AV SAMLING……………………………………...……100
KONKLUSJON
APPLIKASJON…………………………………………………………………………………105
FAGINDEKS……………………………………………………….…….…115
Introduksjon
Lingvistikk- vitenskapen om språk. Matematisk lingvistikk- en vitenskap som omhandler formelle metoder for å konstruere og lære språk.
Teori om formell grammatikk- en del av matematisk lingvistikk, inkludert metoder for å beskrive formelle grammatikker for språk, konstruere metoder og algoritmer for å analysere tilhørigheten av kjeder til et språk, samt algoritmer for å oversette algoritmiske språk til maskinspråk.
Drivkraften for opprettelsen og forbedringen av denne teorien var utviklingen av datateknologi og, som en konsekvens, behovet for kommunikasjonsmidler mellom en person og en datamaskin. I alle applikasjoner må datamaskinen forstå et språk der brukeren kan kommunisere til den algoritmer for å løse problemer og innledende data. Hver datamaskin har sitt eget språk med maskininstruksjoner, representert i binær kode og gjenspeiler individuelle prosessoroperasjoner. I de første stadiene av utviklingen av datateknologi kommuniserte programmerere med datamaskiner på dette primitive språket, men mennesker er ikke i stand til å tenke godt når det gjelder maskinens digitale språk. Automatisering av programmering førte til opprettelsen av først sammenstillingsspråk, og deretter algoritmiske språk på høyt nivå, hvorfra oversettelsen til det opprinnelige maskinspråket ble betrodd selve datamaskinen. Slike oversettelsesprogrammer kalles kringkastere.
Mange programvareutviklere står overfor problemet med å forklare språk til en maskin. Det ligger i menneskets natur å finne opp nye språk. Her snakker vi ikke bare om komplekse kompilatorer for nye algoritmiske programmeringsspråk. Ethvert automatisert system må forstå et inndataspørringsspråk. Ny informasjonsteknologi innebærer involvering av sluttbrukeren (vitenskapsmann, designer, teknolog, operatør) - en spesialist på et spesifikt felt, og ikke innen datateknologi og programmeringsteknologi, i å løse problemene deres på en datamaskin. For å få en løsning av høy kvalitet på dette problemet, må det eksistere et intelligent grensesnitt mellom brukeren og datamaskinen: brukeren må stille problemer og oppnå resultatene av løsningen deres i forhold til fagområdet som er kjent for ham. Det vil si at det er nødvendig å utvikle et bredt spekter av domenespesifikke språk. En programvarespesialist må vite hvordan språk lages og deres programvarestøtte.
For å forklare språk til en maskin, må vi ha en klar forståelse av hvordan den fungerer og hvordan vi forstår den. Når vi tenker på det, ser vi at vi ikke vet hvordan vi forstår morsmålet vårt. Prosessen med denne forståelsen er underbevisst og intuitiv. Men for å lage en oversetter, er det nødvendig å ha en algoritme for å oversette tekst til handlingene som denne teksten krever å utføres, og dette krever igjen språk formalisering. Språkformaliseringsproblemene løses av matematisk lingvistikk. Naturlige språk er for komplekse og det er ennå ikke mulig å formalisere dem fullstendig. Algoritmiske språk er tvert imot allerede opprettet med formalisering i tankene. Teorien om formelle språk er den mest utviklede grenen av matematisk lingvistikk, som i hovedsak representerer en teknikk for å forklare språk til en maskin. Før vi ser på definisjonene, modellene og metodene til denne teorien, la oss se på noen konsepter ved å bruke eksempler fra naturlige språk.
Språk- et sett med setninger (fraser) konstruert i henhold til visse regler.
Grammatikk- et sett med regler som bestemmer om en frase tilhører et språk.
Ethvert språk må tilfredsstille egenskapene avgjørbarhet og entydighet.
Språk er løselig, hvis det på en begrenset tid er mulig å fastslå at en frase eller setning tilhører språket. Språket er entydig, hvis noen frase blir forstått på en unik måte.
Hoveddelene av grammatikk er syntaks og semantikk.
Syntaks- et sett med regler som bestemmer riktig konstruksjon av setninger i et språk.
Semantikk- et sett med regler som bestemmer den semantiske eller semantiske riktigheten av setninger i et språk.
En setning kan være syntaktisk korrekt og semantisk feil.
Syntaks forenkles vanligvis av det faktum at ikke alle fraser i et språk trenger å gi mening. Det er ofte vanskelig å forstå meningen med futurister eller talen til enkelte politikere. I denne forbindelse er eksemplet med akademiker L.V. Shcherba interessant: "Glokka kuzdra shteko har skallet bokr og krøller bokrenka." Dette er en setning på russisk, siden den kan analyseres av medlemmene av setningen, men betydningen er uklar.
Den syntaktiske analysen av en frase kan skrives i form av et parse-tre. Treets noder, som subjekt, predikat, subjektgruppe, setning tilsvarer syntaktiske begreper, og bladene er ordene som setningen er bygget opp fra. Ved å kutte av noen av bladene og grenene i et tre får vi en setningsform (en utleibar kjede).
<предложение>
Naturen til setningens tvetydighet kan forklares ved å bruke eksemplet med det samme analysetreet for setningen "Mor elsker datteren sin."
Denne setningen er tvetydig fordi den har to analyseringsalternativer. Syntaktisk tvetydighet innebærer direkte semantisk tvetydighet. Men du kan også gi eksempler på syntaktisk entydige fraser som kanskje ikke blir forstått på grunn av den tvetydige betydningen av ordene. La oss huske at det algoritmiske språket må være entydig.
Et formelt språk er en matematisk abstraksjon som oppsto som en generalisering av vanlige språklige begreper i naturlige språk. Teorien om formelle språk studerer hovedsakelig syntaksen til språk og er grunnlaget for syntaktisk kontrollerte oversettelsesprosesser, som inkluderer oversettelse, montering og kompilering. Grunnlaget for denne teorien ble lagt av den amerikanske matematikeren N. Chomsky på slutten av 50-tallet og begynnelsen av 60-tallet og fortsetter å utvikle seg til i dag sammen med utviklingen av datateknologi. La oss dvele ved hovedelementene i denne teorien.