I matematikk , informatikk og lingvistikk er et formelt språk et sett med ord . Alfabetet til et formelt språk er settet med symboler, bokstaver eller leksemer som brukes til å konstruere språkets ord; ofte antas det at dette alfabetet er ferdig. Den Målet med formelle språkteori er å beskrive formelle språk.
Ord er sekvenser av elementer i dette alfabetet; ord som tilhører et bestemt formelt språk kalles noen ganger velformede ord eller velformede formler . Et formelt språk defineres ofte av en formell grammatikk , for eksempel algebraiske grammatikker, og analyseres av automata .
Teorien om formelle språk studerer de rent syntaktiske aspektene ved slike språk, det vil si deres formelle interne struktur. Språkteori stammer fra lingvistikk , som et middel til å forstå de syntaktiske regelmessighetene til naturlige språk :
Studiet av formelle språk inkluderer alle metodene for beskrivelse og analyse av disse språkene, for eksempel formelle grammatikker for generering og automatikk for anerkjennelse, men det er også interessert i maskinlæring og oversettelse . Innen oversettelsesområdet gjelder språkteori programmeringsspråk kompilatorer .
Vi gir oss et sett , kalt et alfabet der elementene kalles bokstaver .
Denne loven om intern komposisjon er assosiativ og innrømmer det tomme ordet for nøytralt element (som rettferdiggjør notasjonen ). Følgelig er settet , utstyrt med denne loven, en monoid . Det er en fri monoid i betydningen algebra.
Et formelt språk er et sett med ord på et endelig alfabet, det vil si en del av det frie monoidet på dette alfabetet.
Noen eksempler på formelle språk:
Et formelt språk kan spesifiseres på forskjellige måter. Det som søkes er en endelig og eksplisitt metode eller mekanisme som gjør det mulig å produsere eller analysere et generelt uendelig språk. Blant disse metodene er det:
Typiske spørsmål vi stiller oss om et formelt språk er følgende:
Disse spørsmålene har koblinger til beregningsevne og kompleksitetsteori .
Språk er gruppert i språkfamilier. Chomsky-hierarkiet gir oss fire typer grammatikk, hver type grammatikk genererer en språkfamilie.
Disse språksettene er alle inkludert i hverandre og er gitt her fra det største settet til det minste. Så alt rasjonelt språk er algebraisk , som i seg selv er kontekstuelt , som i seg selv er rekursivt opptelt .
Mellom disse 4 språkfamiliene kan man merke familier som ikke er en del av Chomsky-hierarkiet, men som forblir bemerkelsesverdige av definisjonene og egenskapene. De deterministiske kontekstfrie språkene er språkene som er anerkjent av automatisk deterministisk stabel , og er strengt tatt med i familien av algebraiske språk. De rekursive språkene er språkene som er gjenkjent av en Turing-maskin, og hvis komplement også er anerkjent av en Turing-maskin. De er derfor strengt tatt med i rekursivt tallrike språk .
Flere operasjoner kan brukes til å lage nye språk fra gitte språk. Anta at L og M er språk på noe vanlig alfabet.
Den mengdeoperasjoner kryss , union og komplemente er definert som for hvilket som helst sett.
Den sammensetning av L og M , bare bemerket er det sett av ord på formen xy der x er et ord av L og det er et ord av M .
Den kvotient til venstre av et ord er det sett av ord som tilhører . Kvotienten til venstre kalles også rest .
Den kvotient til høyre av et ord defineres symmetrisk som det sett av ord som hører til .
Den kvotient til venstre og kvotienten til høyre utvide til språk. Dermed er kvotienten til venstre for et språk , betegnet , foreningen av språkene for i .
Den Kleene stjerne av L er den sett merke sammensatt av ordene i skjemaet med og . Dette settet inneholder ordet tomt .
Det motsatte av L , bemerket eller inneholder speilordene til ordene til L , det vil si ordene til L lest fra høyre til venstre.
Den blanding av L og M , betegnet L Ш M er et sett med ord som kan skrives der og er ord (muligens tøm) som et ord av L og enten et ord fra M . For eksempel Ш .
En applikasjon er en morfisme eller homomorfisme hvis for alle ord av . Det homomorfe bildet av et språk på er settet
.Ved misbruk av språk kaller vi omvendt morfisme omvendt av en morfisme. Den inverse av morphism er betegnet funksjon av i settet av deler av definert av
.Det er generelt ikke en morfisme. Bildet av en omvendt morfisme av et språk på er språket
.En morfisme er ikke å slette eller øke, eller, etterligning av engelsk, ε-fri hvis bildet av et brev aldri er det tomme ordet. I dette tilfellet er lengden på bildet av et ord større enn eller lik ordets.
Et vanlig spørsmål om disse operasjonene er å kjenne de avsluttende egenskapene til hver språkfamilie for hver av disse operasjonene, dvs. hvis språket som kommer fra en operasjon forblir i samme språkfamilie som språkene han kommer fra.
Rasjonelle språk |
Deterministiske algebraiske språk |
Algebraiske språk |
Kontekstuelle språk |
Rekursive språk |
Rekursivt tallrike språk |
|
---|---|---|---|---|---|---|
Union | Lukket | Ingen gjerde | Lukket | Lukket | Lukket | Lukket |
Kryss | Lukket | Ingen gjerde | Ingen gjerde | Lukket | Lukket | Lukket |
Utfyllende | Lukket | Lukket | Ingen gjerde | Lukket | Lukket | Ingen gjerde |
Sammenkobling | Lukket | Ingen gjerde | Lukket | Lukket | Lukket | Lukket |
Star of Kleene | Lukket | Ingen gjerde | Lukket | Lukket | Lukket | Lukket |
Speil | Lukket | Ingen gjerde | Lukket | Lukket | Lukket | Lukket |
Blandet | Lukket | Ingen gjerde | Ingen gjerde | Ingen gjerde | Ingen gjerde | Ingen gjerde |
Morfisme | Lukket | Ingen gjerde | Lukket | Ingen gjerde | Ingen gjerde | Lukket |
Voksende morfisme | Lukket | Ingen gjerde | Lukket | Lukket | Lukket | Lukket |
Omvendt morfisme | Lukket | Lukket | Lukket | Lukket | Lukket | Lukket |