Basisvideo Formale Sprachen
Unter dem Video findet sich ein, passagenhaft fehlerbereinigtes oder gekürztes, auf meinem freien Vortrag basierendes Transkript, welches zum Nachlesen einzelner Passagen ohne Spulen und Suchen genutzt werden kann.
Weiteres Video zu regulären Sprachen und endlichen Automaten folgt und wird dann hier verlinkt
Aufbau einer formalen Sprache
Formale Sprachen in der Informatik sind einerseits Wörter, diese sind zusammengesetzt aus Zeichen, also aus dem Alphabet, quasi aus Buchstaben.
Weil Zeichen werden zusammengesetzt zu Zeichenketten.
Und natürlich aus gewissen Regeln, das heißt eine formale Sprache ist genau wie Deutsch und Englisch eine Sprache die gewissen Regeln folgt, also der Grammatik der Sprache.
In dem Kontext einer formalen Sprache oder einer Sprache generell ist es dann auch noch wichtig zu wissen was Syntax und Semantik bedeuten.
Die Syntax ist allgemein; z.B. in einer Programmiersprache, wenn man diese verletzt kann das Programm nicht richtig kompiliert und ausgeführt werden.
Die Syntax in einer natürlichen Sprachen wie z.B. Deutsch sorgt einfach mitunter für einen unverständlichen Satz.
Die Semantik ist dann wieder etwas anderes, wenn etwas syntaktisch richtig ist aber semantisch falsch, also beispielsweise ein deutscher Satz der zwar grammatikalisch richtig ist aber überhaupt keinen Sinn hat, z.B. "Der Apfel ist schnell." Das ist ein richtiger Satz, das kann man so sagen, aber es hat nicht wirklich einen Sinn. Das gleiche geht in Programmiersprachen auch, man kann Programme schreiben die richtig funktionieren [eher komplett durchlaufen] aber nichts wirkliches machen oder wo am Ende irgendein Stuss herauskommt.
Definition von formalen Sprachen
Formale Sprachen sind zusammengesetzt aus einer Nenge der Terminale, der Nichtterminale, einer Startvariable; das ist nicht wirklich ein Bestandteil der Definition aber man braucht eine Startvariable, die Teil der Nichtterminale ist; man nimmt häufig S.
Und man braucht die Produktionsregeln. So, was ist das alles?
Die Terminale sind eine Menge von Zeichen, beispielsweise '1', '2', '3', 'a', 'b', 'c', die quasi am Ende da stehen; also die Terminale kann sich so merken: terminiert, danach kommt nichts mehr.
Die Nichtterminale sind nicht terminiert, also sie werden noch weiter aufgelöst, weiter verarbeitet.
Die Startvariable ist ein Nichtterminal weil man mit S anfängt, man kann ja nicht am Anfang direkt aufhören.
Und die Produktionsregeln sind die Regeln der Syntax, die Regeln der Grammatik; was man jetzt quasi damit machen muss. Also, was ist das jetzt alles?
Syntax der Definition & Beispiel für eine formale Sprachen
Diese beiden Abschnitte guckt man sich am besten im Video an, da dort schrittweise eingeblendet und erklärt wird.
Weiterführendes
Mit einer formalen Sprache kann man mit einer Menge an Terminalen und Nichtterminalen und gewissen Vorschriften beliebige [Ausdrücke/Wörter]; ja quasi alles generieren.
Reguläre Sprachen
Es gibt aber auch noch formale Sprachen in einer besonderen Form, also die regulären Sprachen. Diese sind eine besondere Einschränkung mit denen dann noch andere Konstrukte möglich sind. [...]
Endliche Automaten
Was viel interessanter ist sind die endlichen Automaten, das ist quasi die Umkehrung von formalen Sprachen. Das heißt mit formalen Sprachen kann man nur diese ganzen Ausdrücke generieren.
Mit endlichen Automaten; also zu jeder regulären Sprachen kann man einen endlichen Automaten entwickeln.
Also die formale Sprache muss gewisse Einschränkungen haben damit Sie mit einem Automaten dargestellt werden kann.
Also ein Automat akzeptiert quasi diese Sprache [vielmehr die Wörter/Ausdrücke die mit dieser regulären Sprache generiert wurden].
Das heißt man "schiebt" das Wort das man bekommen hat in diesen Automaten rein und der sagt einem dann ob dieses Wort, was man da rein geschoben hat, Teil der formalen [eher regulären] Sprache ist, ob es akzeptiert wird. Das ist dann ein Endzustand, wenn es nicht akzeptiert wird, dann landet der Automat in einem Fehlerzustand.
Fragen zu diesem Beitrag? Hier gehts direkt zum passenden Diskussionsforum!
OberPrima gibt es auch bei Google+, folge uns! :)