I matematik , datalogi og lingvistik er et formelt sprog et sæt ord . Alfabetet på et formelt sprog er det sæt symboler, bogstaver eller lexemer, der bruges til at konstruere sprogets ord; ofte antages det, at dette alfabet er færdigt. Den Formålet med formelle sprog teori er at beskrive formelle sprog.
Ord er sekvenser af elementer i dette alfabet; ord, der hører til et bestemt formelt sprog kaldes undertiden velformede ord eller velformede formler . Et formelt sprog defineres ofte af en formel grammatik , såsom algebraiske grammatikker, og analyseres af automata .
Teorien om formelle sprog studerer de rent syntaktiske aspekter af sådanne sprog, det vil sige deres formelle interne struktur. Sprogteori stammer fra lingvistik som et middel til at forstå de syntaktiske regelmæssigheder i naturlige sprog :
Studiet af formelle sprog inkluderer alle midlerne til beskrivelse og analyse af disse sprog, såsom formelle grammatikker til generation og automater til anerkendelse, men det er også interesseret i maskinindlæring og oversættelse . På området for oversættelse, sprog teori gælder for programmeringssprog compilere .
Vi giver os selv et sæt , kaldet et alfabet, hvis elementer kaldes bogstaver .
Denne lov om intern sammensætning er associerende og indrømmer det tomme ord for neutralt element (som retfærdiggør notationen ). Derfor er sættet , der følger med denne lov, en monoid . Det er en fri monoid i betydningen algebra.
Et formelt sprog er et sæt ord på et endeligt alfabet, det vil sige en del af det frie monoid på dette alfabet.
Nogle eksempler på formelle sprog:
Et formelt sprog kan specificeres på forskellige måder. Det, der søges, er en endelig og eksplicit metode eller mekanisme, der gør det muligt at producere eller analysere et generelt uendeligt sprog. Blandt disse metoder er der:
Typiske spørgsmål, som vi stiller os selv om et formelt sprog, er følgende:
Disse spørgsmål har sammenhæng med beregnings- og kompleksitetsteori .
Sprog er grupperet i sprogfamilier. Chomsky-hierarkiet giver os fire typer grammatik, hvor hver type grammatik skaber en sprogfamilie.
Disse sprog sæt er alle inkluderet i hinanden og er givet her fra det største sæt til det mindste. Så alt rationelt sprog er algebraisk , hvilket i sig selv er kontekstuelt , hvilket i sig selv rekursivt kan tælles .
Mellem disse 4 sprogfamilier kan man bemærke familier, der ikke er en del af Chomsky-hierarkiet, men som forbliver bemærkelsesværdige ved deres definitioner og deres egenskaber. De deterministiske kontekstfrie sprog er de sprog, der genkendes af automata deterministisk stak og er strengt inkluderet i familien af algebraiske sprog. De rekursive sprog er de sprog, der genkendes af en Turing-maskine, og hvis komplement også anerkendes af en Turing-maskine. De er derfor strengt inkluderet i rekursivt talbare sprog .
Flere operationer kan bruges til at skabe nye sprog fra givne sprog. Antag at L og M er sprog på et almindeligt alfabet.
Den sætoperatorer vejkryds , union og komplementering er som defineret for ethvert sæt.
Den sammenkædning af L og M , netop bemærket er det sæt af ord af formen xy , hvor x er et ord af L , og der er et ord af M .
Den kvotienten til venstre af et ord er det sæt af ord som tilhører . Kvotienten til venstre kaldes også rest .
Den kvotienten til højre for et ord er defineret symmetrisk som det sæt af ord som hører til .
Den kvotienten til venstre og kvotienten på højre omfatte sprog. Således er kvotienten til venstre for et sprog , bemærket , foreningen af sprogene for i .
Den Kleene stjerne af L er det sæt bemærket sammensat af ord af formen med og . Dette sæt indeholder ordet tomt .
Det modsatte af L , bemærket eller indeholder spejlordene for ordene L , det vil sige ordene fra L, der læses fra højre mod venstre.
Den blanding af L og M , betegnet L Ш M er sæt ord, der kan skrives hvor og er ord (muligvis tom) som enten et ord af L og enten et ord fra M . F.eks Ш .
En applikation er en morfisme eller homomorfisme si for alle ord af . Det homomorfe billede af et sprog på er sættet
.Ved misbrug af sprog kalder vi omvendt morfisme omvendt af en morfisme. Den omvendte morfisme af er den betegnede funktion af i det sæt af dele, der er defineret af
.Det er generelt ikke en morfisme. Billedet af en omvendt morfisme af et sprog på er sproget
.En morfisme slettes ikke eller øges, eller efterligning af engelsk, ε-fri, hvis billedet af et brev aldrig er det tomme ord. I dette tilfælde er billedets længde større end eller lig med ordets længde.
Et almindeligt spørgsmål om disse operationer er at kende de lukkende egenskaber for hver sprogfamilie for hver af disse operationer, dvs. hvis sproget, der er resultatet af en operation, forbliver i den samme sprogfamilie som de sprog, hvis han kommer fra.
Rationelle sprog |
Deterministiske algebraiske sprog |
Algebraiske sprog |
Kontekstuelle sprog |
Rekursive sprog |
Rekursivt talbare sprog |
|
---|---|---|---|---|---|---|
Union | Lukket | Intet hegn | Lukket | Lukket | Lukket | Lukket |
Vejkryds | Lukket | Intet hegn | Intet hegn | Lukket | Lukket | Lukket |
Supplerende | Lukket | Lukket | Intet hegn | Lukket | Lukket | Intet hegn |
Sammenkædning | Lukket | Intet hegn | Lukket | Lukket | Lukket | Lukket |
Star of Kleene | Lukket | Intet hegn | Lukket | Lukket | Lukket | Lukket |
Spejl | Lukket | Intet hegn | Lukket | Lukket | Lukket | Lukket |
Blandet | Lukket | Intet hegn | Intet hegn | Intet hegn | Intet hegn | Intet hegn |
Morfisme | Lukket | Intet hegn | Lukket | Intet hegn | Intet hegn | Lukket |
Voksende morfisme | Lukket | Intet hegn | Lukket | Lukket | Lukket | Lukket |
Omvendt morfisme | Lukket | Lukket | Lukket | Lukket | Lukket | Lukket |