Formelt språk

Et formelt språk er et abstrakt språk der det, i motsetning til naturlige språk, ofte ikke er kommunikasjon som er i forgrunnen, men matematisk bruk. Et formelt språk består av et visst antall symbolstrenger (generelt tegnstrenger ) ("ord" i språket), som kan settes sammen fra et sett med tegn / symboler ("alfabet", grunnleggende symboler). Formelle språk brukes i lingvistikk , logikk og teoretisk informatikk .

Formelle språk er egnet for (matematisk) presis beskrivelse av håndtering av tegnstrenger. For eksempel kan dataformater eller hele programmeringsspråk spesifiseres. Sammen med formell semantikk får de definerte karakterstrengene en (matematisk) betydning. I et programmeringsspråk kan en programmeringsinstruksjon (som en del av det formelle språket) tildeles en unik maskinadferd (som en del av semantikken ).

Basert på formelle språk kan imidlertid også logiske beregninger defineres som matematiske konklusjoner kan trekkes med. I forbindelse med formelt definerte programmeringsspråk kan kalkulasjoner bidra til å sjekke programmene for korrekthet .

definisjon

En formspråk over en alfabetet er en undergruppe av kløver aske skall av alfabetet: . ${\ displaystyle L}$${\ displaystyle \ Sigma}$${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

Et alfabet definerer tegnene som et " ord " i språket kan dannes fra. For eksempel kan du opprette desimalrepresentasjonen av et hvilket som helst naturlig tall fra alfabetet . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {0,1,2,3,4,5,6,7,8,9 \}}$

Alle ord med en endelig lengde (lengde 0 eller lengre) som vilkårlig kan dannes fra et gitt alfabet, og som hver enkelt bokstav er et element av , denne størst mulige mengden ord for alfabetet , kalles Kleens skall av alfabetet kort sagt . Et formelt språk over et alfabet er derfor en viss delmengde av Kleene-skallet i alfabetet ditt - generelt er ikke alle vilkårlige kombinasjoner av tegn et gyldig ord på språket. ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {*}}$${\ displaystyle \ Sigma}$

Formelle språk kan være tomme, endelige eller uendelige; på det meste kan de omfatte hele Kleenesche-skallet i alfabetet. De kan defineres av en matematisk tilstand på deres ord: "Språket ... er settet med alle ord som ..." gjelder for.

Språkene som brukes i teoretisk informatikk er imidlertid vanligvis mer spesifikt definert av en bestemt erstatningsprosedyre - regler om hvordan alfabettegnene er / kan kombineres. Det finnes forskjellige typer erstatningsmetoder: Semi-Thue-systemer , Chomsky-grammatikker , Lindenmayer-systemer og andre. Slike erstatningsprosesser er for eksempel basert på en spesifikk startkarakterstreng som gradvis blir konvertert til ordstrukturer gjennom gjentatt (“rekursiv”) anvendelse av reglene (tekstutskiftninger), som da som en helhet, eller bare en spesifisert seksjon. der, ettersom ord gjelder språket. Man snakker også om generative grammatikker her , fordi ordene til et språk genereres trinn for trinn via slike tekstutskiftninger . Motsatt kan språk også defineres som settet med alle ord som et bestemt forhåndsdefinert ord eller et av flere forhåndsdefinerte ord kan genereres fra (via språkutskiftingsprosessen). ("Alt tilhører språk som kan spores tilbake til ... gjennom reglene.")

Differensiering fra naturlige språk

Ved hjelp av formelle språk kan naturlige språk også modelleres, spesielt syntaksen. Når man sammenligner formelle språk med naturlige språk, bør det imidlertid bemerkes at naturlige språk har minst de to overliggende hierarkiske nivåene av ordet og setningen over de elementære fonetiske tegnene . Reglene for deres struktur er vanligvis delt inn i morfologi på den ene siden og syntaksen på den andre. På formelle språk er det derimot ofte bare ett nivå av hierarkiet til det formelle ordet over det elementære alfabettegnet ; når det gjelder ordstrukturen, snakker man om syntaksen. Hvis et naturlig språk modelleres med et formelt språk, kalles setningene til det naturlige språket ord fra et formelt synspunkt .

I tillegg har ytringer i naturlig språk en naturlig betydning, mens betydningen av formelle språk alltid må defineres på en formell måte.

Eksempler

1. Det programmeringsspråk C er et formelt språk. Ordene fra C er de respektive programmene. Alfabetet til C er nøkkelordene og tegnene som er angitt i definisjonen av C.
2. De naturlige tallene i unary representasjon: ${\ displaystyle \ mathbb {N} _ {\ rm {un}}: = \ {\ varepsilon, 1,11,111,1111, \ ldots \}}$
3. Det unare språket ovenfor , som bare inneholder ord med firkantet lengde:${\ displaystyle \ {a \}}$${\ displaystyle {\ rm {quad \ _count}}: = \ {a ^ {(n ^ {2})} \ mid n \ in \ mathbb {N} \}}$
4. ${\ displaystyle {\ rm {count}} _ {2}: = \ {a ^ {n} b ^ {n} \ mid n \ in \ mathbb {N} \}}$
5. ${\ displaystyle {\ rm {count}} _ {3}: = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ in \ mathbb {N} \}}$
6. Språket i alle palindromes : , hvor den refleksjon av ordet er.${\ displaystyle {\ rm {pal}}: = \ {w \ in \ {0.1 \} ^ {*} \ mid w = w ^ {R} \}}$
   ${\ displaystyle w ^ {R}}$${\ displaystyle w}$
7. Den desimal koding av primtall: . Her betegner kodingen av de naturlige tallene i desimalsystemet, og PRIM står for settet med primtall .${\ displaystyle {\ rm {prim}} _ {\ rm {dec}}: = \ {{\ rm {dec}} (p) \ mid p \ i {\ rm {PRIM}} \}}$
   ${\ displaystyle {\ rm {dec}} \ colon \ mathbb {N} \ rightarrow \ {0,1,2,3,4,5,6,7,8,9 \} ^ {*}}$
8. Den Morse eller Thue sekvens : , hvori en homomorfi er definert som følger: og , . Dermed er de første elementene i Thue-sekvensen: 0, 01, 0110, 01101001, 0110100110010110 ...${\ displaystyle {\ rm {thue}}: = \ {h_ {t} ^ {n} (0) \ mid n \ in \ mathbb {N} \}}$
   ${\ displaystyle h_ {t}}$${\ displaystyle h_ {t} (\ varepsilon) = \ varepsilon}$${\ displaystyle h_ {t} (w0): = h_ {t} (w) 01}$${\ displaystyle h_ {t} (w1): = h_ {t} (w) 10}$
   

Operasjoner på formelle språk

To språk over alfabetet og over alfabetet er banale, begge språkene er også over , det vil si sett med ord . Derfor er også ${\ displaystyle L_ {1}}$${\ displaystyle \ Sigma _ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle \ Sigma _ {2}}$${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$${\ displaystyle (\ Sigma _ {1} \ cup \ Sigma _ {2}) ^ {*}}$

• den union ${\ displaystyle L_ {1} \ cup L_ {2}}$
• den gjennomsnittlige ${\ displaystyle L_ {1} \ cap L_ {2}}$
• den forskjellen ${\ displaystyle L_ {1} \ setminus L_ {2}}$

Språk om . ${\ displaystyle \ Sigma _ {1} \ cup \ Sigma _ {2}}$

Ytterligere operasjoner på språk er:

Sammenkobling

Den sammensetning av to språk og er språket av ordene som er skapt ved å skrive ett ord etter hverandre ( sammensetning ) fra og fra : ${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$${\ displaystyle u}$${\ displaystyle L_ {1}}$${\ displaystyle v}$${\ displaystyle L_ {2}}$

${\ displaystyle L_ {1} \ circ L_ {2}: = \ {uv \ mid u \ in L_ {1}, v \ in L_ {2} \}}$.

Forbindelsene til forskjellige språk over alfabetet er for eksempel : ${\ displaystyle \ Sigma = \ {a, \, b \}}$

${\ displaystyle \ {a \} \ circ \ {ab \} = \ {aab \}}$

${\ displaystyle \ {a, \, bb \} \ circ \ {aa, \, b \} = \ {aaa, \, ab, \, bbaa, \, bbb \}}$

${\ displaystyle \ {abb, \, bab \} \ circ \ {\ varepsilon, \, aab, \, bb \} = \ {abb, \, bab, \, abbaab, \, babaab, \, abbbb, \ , babbb \}}$

Det nøytrale elementet i sammenkobling er språk, som bare inneholder det tomme ordet . Følgende gjelder for ethvert språk : ${\ displaystyle L}$

${\ displaystyle L \ circ \ {\ varepsilon \} = \ {\ varepsilon \} \ circ L = L}$

Det absorberende elementet i sammenkoblingen er tomt språk, slik at for hvert språk : ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$

${\ displaystyle L \ circ \ {\} = \ {\} \ circ L = \ {\}}$

Sammenslåingen av språk, som sammenkoblingen av ord, er assosiativ , men ikke kommutativ . For eksempel:

${\ displaystyle (\ {a, \, bab \} \ circ \ {a, \, b \}) \ circ \ {ab \} = \ {a, \, bab \} \ circ (\ {a, \ , b \} \ circ \ {ab \}) = \ {aaab, \, abab, \, babaab, \, babbab \}}$

men:

${\ displaystyle \ {a, \, bab \} \ circ \ {a, \, b \} = \ {aa, \, ab, \, baba, \, babb \} \ not = \ {aa, \, abab, \, ba, \, bbab \} = \ {a, \, b \} \ circ \ {a, \, bab \}}$

I tillegg, siden den kraft settet av Kleen s konvolutt av en hvilken som helst alfabetet (som er lik mengden av alle språk som kan dannes fra ) er stengt med hensyn til sammensetning, danner den en monoid sammen med den sammenkjedingen som operatøren og språket av det tomme ordet som det nøytrale elementet . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$

makt

Den kraften i et språk er fold sammensetning av dette språket med seg selv Det er definert rekursivt med.: ${\ displaystyle L ^ {n}}$${\ displaystyle n}$

${\ displaystyle L ^ {0}: = \ {\ varepsilon \}}$

${\ displaystyle L ^ {n + 1}: = L ^ {n} \ circ L}$   (for )${\ displaystyle n \ in \ mathbb {N} _ {0}}$

For eksempel:

${\ displaystyle \ lbrace aa, \, abab, \, bbab, \, ba \ rbrace ^ {0} = \ lbrace \ varepsilon \ rbrace}$

${\ displaystyle \ lbrace a, \, b \ rbrace ^ {2} = \ lbrace a, \, b \ rbrace ^ {1} \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace a , \, b \ rbrace ^ {0} \, \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = (\ lbrace \ varepsilon \ rbrace \ , \ circ \, \ lbrace a, \, b \ rbrace) \, \ circ \, \ lbrace a, \, b \ rbrace = \ lbrace aa, \, ab, \, ba, \, bb \ rbrace}$

${\ displaystyle \ lbrace a \ rbrace ^ {4} = \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace \, \ circ \, \ lbrace a \ rbrace = \ lbrace aaaa \ rbrace}$

Spesielt gjelder følgende for hvert enkelt element, formelle språk (med ) og hvert : ${\ displaystyle L = \ lbrace w \ rbrace}$${\ displaystyle w \ in \ Sigma ^ {\ ast}}$${\ displaystyle n \ in \ mathbb {N} _ {0}}$

${\ displaystyle L ^ {n} = \ lbrace w \ rbrace ^ {n} = \ lbrace w ^ {n} \ rbrace}$

Kleene - * - grad og Kleene - + - grad

Den Kleene - * - lukking (Kleene konvolutt, også kalt iterasjon ) og den Kleene - + - lukking (positiv konvolutt) av et formelt språk er definert ved foreningen av kraft språk i : ${\ displaystyle L ^ {*}}$ ${\ displaystyle L ^ {+}}$${\ displaystyle L}$${\ displaystyle L}$

${\ displaystyle L ^ {*}: = \ bigcup _ {i \ in \ mathbb {N} _ {0}} L ^ {i}}$

 

${\ displaystyle L ^ {+}: = \ bigcup _ {i \ in \ mathbb {N}} L ^ {i}}$

Viktige formelle språkkurs

1. I 1956 etablerte Noam Chomsky et hierarki av formelle grammatikker som produserer forskjellige typer formelle språk. Dette er i dag kjent som Chomsky-hierarkiet . Det skilles mellom type 0, type 1, type 2 og type 3: rekursivt opptellbare , kontekstsensitive , kontekstfrie og vanlige språk.
2. Aristid Lindenmayer foreslo et kontrollsystem der utskiftingstrinn utføres parallelt ved hvert trinn på hvert punkt. Disse systemene kalles Lindenmayer-systemer .
3. Med semi-Thue-systemer kan det settes språk som er avledet fra startord.
4. Med Church-Rosser-systemene forklarer språkene deres ord å bli redusert til et terminalord.
5. Termomskrivingssystemer genererer settet med vilkår som tilsvarer en startperiode.
6. Vi får generaliseringer av formelle språk med graf grammatikker som vi kan generere graf språk.
7. Hypergraph-grammatikker produserer hypergraphs , en generalisering av grafer.

Historisk

Gottlob Freges konseptuelle skriving regnes som et av de første formelle språkene , ett slik Frege skrev "the language of formulas of pure thought". Axel Thues Semi-Thue-system , som ble introdusert i 1914 og kan brukes til å transformere strenger, påvirket også utviklingen av formelle grammatikker.

Sitat

Dagens grunnleggende forskning er mestret

Heinrich Scholz møtte Konrad Zuse i 1944 , som jobbet med planplanen sin som en del av doktorgradsavhandlingen . I mars 1945 uttrykte Scholz sin takknemlighet for anvendelsen av sin logiske beregning.

Se også

• konstruert språk
• Dataspråk
• Kategori: Formelt språk - Liste over formelle språk

Søknader se i:

• Beregnbarhetsteori
• Kompleksitetsteori
• Kryptografi
• Kryptanalyse
• Kompilator konstruksjon

litteratur

• Lars Peter Georgie: Forutsigbarhet, kompleksitet, logikk . Vieweg, Braunschweig / Wiesbaden,
  • En tredje utgave dukket opp i 1995.
  • Engelsk utgave: Computability, Complexity, Logic . Publisert i serien: Studier i logikk og grunnlaget for matematikk . Nord-Holland, Amsterdam 1985.

En presentasjon av formelle språk i sammenheng med beregbarhetsteori, logikk og kompleksitetsteori. Stiller høye krav til leseren, men gir dyp innsikt.

• Michael A. Harrison: Introduksjon til formell språkteori . Publisert i serien: Series in Computer Science. Addison-Wesley, 1978.

En veldig detaljert og høyt berømt introduksjon.

• John E. Hopcroft og Jeffrey D. Ullman : Introduksjon til Automata Theory, Formal Languages, and Complexity Theory . Addison-Wesley, 1988.
  • Engelsk original: Introduksjon til Automata Theory, Languages ​​and Computation . Addison-Wesley, 1979.
  • En revidert tredje utgave på tysk ble utgitt i 1994 av Oldenbourg R. Verlag GmbH. I 2004 utgav Addison-Wesley en andre reviderte utgave.

Den engelske originalen er den mest siterte boken i teoretisk informatikk. Bevisene blir av og til feil fremstilt i eldre tyske oversettelser. Denne boken er oversatt til en rekke språk.

• Grzegorz Rozenberg og Arto Salomaa: The Mathematical Theory of L-Systems . Academic Press, New York 1980.

Den mest detaljerte boka om L-systemer.

• Grzegorz Rozenberg og Arto Salomaa (redaktører): Håndbok for formelle språk . Volum I-III, Springer, 1997, ISBN 3-540-61486-9 .

En detaljert oversikt over de viktigste områdene for formelle språk presenteres av akademikere som er aktive i dette området.

• Arto Salomaa: Formelle språk . Springer, 1978.
  • Engelsk original: Formelle språk . Academic Press, 1973.
• Ingo Wegener: Teoretisk informatikk . Teubner, Stuttgart 1993, ISBN 3-519-02123-4 .

I representasjonen av de formelle språkene blir kompleksiteten til de formelle språkkonstruksjonene alltid håndtert. Ellers kan dette bare finnes i originallitteraturen.

• U. Hedtstück: Introduksjon til teoretisk informatikk - formelle språk og automatteori . Oldenbourg Verlag, München 2000, ISBN 3-486-25515-0 .
• S. Abramsky, Dov M. Gabbay, TSE Maibaum (red.): Håndbok for logikk i informatikk. Vol. 5: Logiske og algebraiske metoder. Oxford University Press 2000, ISBN 0-19-853781-6 .
• Mogens Nielsen, Wolfgang Thomas: Computer Science Logic. Springer 1998, ISBN 3-540-64570-5

Individuelle bevis

1. ↑ Chomsky, Noam (1956). "Tre modeller for beskrivelse av språk". IRE-transaksjoner om informasjonsteori (2): 113-124.
2. ↑ Martin Davis (1995). Påvirkninger av matematisk logikk på datavitenskap. I Rolf Herken. Den universelle Turing-maskinen: en undersøkelse fra et halvt århundre. Genser. S. 290. ISBN 978-3-211-82637-9 .
3. ^ Ronald V. Book, Friedrich Otto: String rewriting systems. Springer, 1993, ISBN 0-387-97965-4 , s. 36.
4. ↑ I: Research and Progress No. 35/36, år 1941, s. 382 ff.
5. ↑ Hartmut Petzold : Moderne aritmetiske kunstnere. Industrialiseringen av datateknologi i Tyskland. CH Beck Verlag, München 1992.