Sprachen/Grammatiken/Automaten

Sprache ist eine beliebige Teilmenge der Permutation eines bestimmten Alphbets. Sie laesst sich durch Grammatiken Spezifizieren. Waehrend Sprachen unendlich viele Objekte enthalten, bestehen Grammatiken aus einer beschraenkten Anzahl. Chomsky unterteilte die Grammatiken und somit auch die Sprachen in vier grosse Gruppen. Jede der nun folgenden Gruppen ist in der vorherigen echt enthalten und somit Teilmenge dieser. Die von Chomsky angesetzte Obermenge aller Sprachen ist vom Typ 0. Die korrespondierende Grammatik nennt man Phrasengrammatik. Sie unterliegt keinen Einschraenkungen. Bildet man eine Teilmenge von diesen Sprachen, wobei die zugehoerige Grammatik die Einschraekung |w1| <= |w2| erfuellt, so spricht man von einer Typ1- bzw. kontextsensitiven Sprache. Verschaerft man die Auswahlbedingung |w1|<=|w2| mit der Auflage, dass w1 nur aus einer einzelne Variable bestehen darf, so erhalten wir die Untermenge der Typ2- oder auch kontextfreien Sprachen. Unterwirft man nun diese neueste Teilmenge zusaetzlich der Bedingung, dass w2 entweder aus einem Terminalsymbol oder einem Non-Terminalsymbol und einem Terminalsymbol besteht. Wir erhalten somit die Typ3- bzw. regulaeren Sprachen. Fuer diese verschiedenen Sprachtypen hat man im Laufe der Zeit zusaetzliche hilfreiche Darstellungsmittel entworfen. So z.B. benutzt man fuer die regulaeren Sprachen nicht nur die regulaeren Grammatiken, sondern auch endliche deterministische bzw. nichtdeterministische Automaten, aber auch reguläre Ausdrücke. Für kontextfreie Sprachen nutzt man den Kellerautomaten. Der linear beschränkte Automat ist das vorrangige Hilfsmittel um kontextsensitive Sprachen besser darstellen zu können, und die Turringmaschine ist wohl die bekannteste äquivalente Darstellungsform von Typ0-Sprachen. Das Problem der Umwandlung eines bestimmten feststehenden Datenformats in ein anderes ist hierbei auf Sprachen, speziell der regulären Sprachen, einzuordnen. Mit Hilfe eines implementierten endlichen deterministeischen Automaten kann die Arbeit stark vereinfacht werden.
P.S.: Diese Zusammenfassung erhebt nicht den Anspruch vollstaendig zu sein. Vielmehrsoll ein Einblick gegeben werden, woher die Idee der Konverterimplementierung stammt.

CSLIB 2000

Zurück: Persönliche Hypertexte