Bestimmen einer Sprache |
| 25.10.2015, 11:39 | Auf diesen Beitrag antworten » |
| Fullmetal | Bestimmen einer Sprache Hallo erstmal, ich studiere Angewandte informatik im 1. Semester und wir sollen nun in einer der Übungsaufgaben aus einer gegeben Grammatik die Sprache herleiten. Allerdings habe ich absolut keine Ahnung wie das funktionieren soll, da unser Professor in der Vorlesung kaum auf die Leute eingeht die noch keine Erfahrung in der Hinsicht haben. Die gegebene Aufgabe lautet: Seien die folgenden beiden Grammatiken gegeben: G1 = (N, T, P1, S) und G2 = (N, T, P2, S) mit N = {S, B}, T = {a, b, c} und P1 = {(S,aB), (S,bB), (B,aS), (B,bS), (B, )} Bestimmen Sie mit Hilfe von Beispielen die Sprache L(G1). Könnte mir vielleicht jemand das ganze anhand dieses Beispieles erklären? LG Fullmetal |
|
|
|
| 25.10.2015, 13:21 | Auf diesen Beitrag antworten » |
| Karlito | Hallo Fullmetal, bei so einfachen Grammatiken kann man die Nichtterminalsymbole als Zustände in einem NEA ansehen. Anhand der Produktionen kann man dann die Übergänge ablesen und den Automaten daraus konstruieren. Es könnte aber auch leichter sein, einfach die ersten Worte der Grammatik selbst zu Produzieren und dann zu schauen, ob man erkennt, welche Sprache sich davon ableitet. Gruß, Karlito |
| 25.10.2015, 15:47 | Auf diesen Beitrag antworten » |
| Fullmetal | Hallo Karlito, vielen Dank erstmal für deine Antwort, auch wenn ich die Hälfte davon leider nicht verstanden habe. Das geht schon bei NEA los, keine Ahnung was das bedeuten soll, bzw was du jetzt genau mit Produktionen meinst. Du hast ja geschrieben die ersten Worte selbs zu produzieren und dann zu schauen ob man die Sprache erkennt, aber genau das ist ja das Problem, ich weiß nicht wie ich diese erstelle. Ich dachte eigentlich das mir vlt jemand ein konkretes Beispiel anhand dieser Aufgabe zeigen könnte, so das ich das dann auch verstehe wie das funktioniert. |
| 25.10.2015, 18:58 | Auf diesen Beitrag antworten » |
| Karlito | Hallo Fullmetal, OK, ich bin naiv davon ausgegangen, dass NEA und DEA bzw. NFA und DFA, also endliche Automaten, ein Begriff sind. Aber Produktionen sollten dir was sagen, da formale Grammatiken über ein 4-Tupel definiert sind, welches wie folgt zusammengesetzt ist. wobei N die Menge der Nichtterminale, T die Menge der Terminalsymbole, P die Menge der Produktionsregeln und S das Startsymbol sind. Eine Produktion ist ein Element der Menge der Produktionsregeln und gibt eine Abbildung an. In unserem Fall (es gibt noch komplexere Grammatiken), welche Nichtterminalsymbole auf welche Folge von Terminal- und NIchtterminalsymbolen abgebildet werden. Nehmen wir ein einfaches Beispiel: Wir haben also nur ein Terminalsymbol "S" , ein Nichtterminalsymbol "a", eine Produktion (S,a) und das Startsymbol ist das NIchtterminalsymbol "S". Das Startsymbol gibt dabei an, von welchem Nichtterminalsymbol aus alle Wörter der Grammatik erzeugt werden. Wir fangen also mit "S" an. Auf Grund unserer Grammatik haben wir nur die Möglichkeit, S auf den Buchstaben "a" abzubilden. Somit enthält unsere Sprache L(G) nur das Wort "a". Gültige Wörter, die durch eine Grammatik erzeugt werden, sind übrigens auch nur Wörter, welche nur Nichtterminale enthalten. Ich gehe davon aus, dass die Letzte Produktion in deiner Sprache "(B, )" bedeuten soll, dass B auf das leere Wort abgebildet wird. Somit müssen alle Wörter, die von der Grammatik erzeigt werden mit der Produktion B enden. Fangen wir also mit S an. S wird ersetzt (abbgebildet) durch aB oder bB. Wird B danach durch das leere Wort ersetzt, dann sind wir fertig. Ansonsten können wir B nur durch aS oder bS ersetzen. Danach müssten wir S wieder ersetzen, da es von S aus keine Produktion gibt, welche nur ein Nichtterminal erzeugt (das leere Wort ist ein Terminal). Somit ist die Sprache Gruß, Karlito |
| Anzeige | |
|
|
|
| 25.10.2015, 21:13 | Auf diesen Beitrag antworten » |
| Fullmetal | Wahnsinn! Ich danke dir für deine Ausführliche und echt Lehrreiche Antwort! Ich habs tatsächlich verstanden 
Vielen, vielen Dank! Lg Fullmetal |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
