Über­blick

Die so­ge­nann­ten for­ma­len Spra­chen sind ein wich­ti­ges Teil­ge­biet der theo­re­ti­schen In­for­ma­tik. Es be­schreibt (in sehr ma­the­ma­ti­scher Prä­gung) Ei­gen­schaf­ten von Wort­men­gen, die als Ein­ga­be von einem In­for­ma­tik­sys­te­me ak­zep­tiert wer­den sol­len. Eine sol­che Wort­men­ge nennt man „Spra­che“. In der Regel muss das In­for­ma­tik­sys­tem mit der Ein­ga­be eine Gül­tig­keits­prü­fung durch­füh­ren („soll die­ses Wort als Ein­ga­be ak­zep­tiert wer­den?“) und/oder die Ein­ga­be in ir­gend­ei­ner Form ver­ar­bei­ten (also ana­ly­sie­ren, in an­de­re Form über­set­zen o.ä.).

Es gibt viele Bei­spie­le für for­ma­le Spra­chen bzw. Soft­ware, die damit um­geht:

• Ein­ga­be­fel­der prü­fen Mail­adres­sen: Eine Ein­ga­be wie „anna@​mail.​de“ soll ak­zep­tiert, „an­naQ­mail.de“ oder „anna@​mail­de“ aber so­fort zu­rück­ge­wie­sen wer­den, weil das keine glo­bal gül­ti­gen Mail­adres­sen sein kön­nen¹ . Eine gül­ti­ge Adres­se ist hier ein „Wort“, die Menge aller gül­ti­gen Mail­adres­sen eine „Spra­che“ im oben ge­nann­ten Sinne.
• Web­brow­ser ver­ar­bei­ten HTML: Der an­ge­lie­fer­te HTML-Quell­text muss zu­erst ana­ly­siert und in­ter­pre­tiert wer­den. Sind die Fra­gen „ist das kor­rek­tes HTML?“ und „was soll ange­zeigt wer­den?“ be­ant­wor­tet, er­zeu­gen sie schließ­lich eine bunte Bildschirm­dar­stel­lung.
• Com­pi­ler über­set­zen Pro­gram­me: Sie neh­men den Quell­text eines Pro­gramms ent­ge­gen, prü­fen auf syn­tak­ti­sche Kor­rekt­heit und über­set­zen es in eine an­de­re Form, die der Com­pu­ter (mehr oder we­ni­ger di­rekt) aus­füh­ren kann.

Mit den for­ma­len Spra­chen un­trenn­bar ver­bun­den ist die zu­ge­hö­ri­ge Theo­rie der Au­to­ma­ten² , wobei Au­to­mat hier eher „Denk­mo­dell“ be­deu­tet als „Ma­schi­ne“. Es gibt un­ter­schied­li­che Klas­sen von Au­to­ma­ten, die ei­ner­seits ma­the­ma­tisch prä­zi­se be­schrie­ben und un­ter­sucht wer­den; an­de­rer­seits kann jeder Typ Au­to­mat je­weils einen be­stimm­ten Typ Spra­chen verarbei­ten. Weil man sie zudem leicht in Soft­ware im­ple­men­tie­ren kann, sind sie in der prak­ti­schen In­for­ma­tik ex­trem nütz­lich.

In ihrer Kom­bi­na­ti­on sind for­ma­le Spra­chen und Au­to­ma­ten ein Grund­pfei­ler der In­for­ma­tik. Der Ab­schnitt 3.3.5 des Bil­dungs­plans für all­ge­mein bil­den­de Gym­na­si­en in Baden-Würt­tem­berg ent­hält im Wesent­lichen re­gu­lä­re und kon­text­freie Spra­chen und die dazu pas­sen­den Typen von Au­to­ma­ten:

¹ Li­bre­Of­fice (mit dem die­ses Do­ku­ment ent­steht) sieht of­fen­bar auch das drit­te Bei­spiel als gül­ti­ge Adres­se an – sie wird daher ohne Zutun des Au­tors in an­de­rer Farbe ge­setzt und mit einem Link auf ein Mail­pro­gramm un­ter­legt.

² Wich­ti­ge Fach­be­grif­fe wer­den bei ihrem ers­ten Auf­tre­ten in­ner­halb die­ses Skripts fett ge­setzt.

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][669 KB]

Wei­ter zu Al­pha­bet, Wort, Spra­che