Schreibweise von L(G) < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:15 So 30.04.2006 | | Autor: | Moe007 |
| Aufgabe | Gegeben ist eine Grammatik G=(V, [mm] \summe, [/mm] P, S) mit V={S,R} und [mm] \summe [/mm] = {a,b} und P= { S [mm] \to [/mm] aRa, [mm] S\to [/mm] bRb, R [mm] \to [/mm] S, R [mm] \to \epsilon}
[/mm]
Gebe L(G) an. |
Hallo Forum,
ich hab ein Problem, wie man L(G) allgemein auf dieses Beispiel angeben soll.
Ich weiß, dass Wörter w [mm] \in [/mm] L(G) sind z.B. : abba, abaaba, baaabbaaab, aaaa, baab etc., also Ketten, die aus den Zeichen a und b bestehen und die symmetisch sind.
Aber wie kann man das allgemein angeben, also ich meine, ich suche einen Term, der alle diese Zeichen beschreibt mit der Symmetrie. Ich kann ja nicht alle möglichen Terme in L(G) aufzählen, das sind ja unendlich viele :)
Leider ist mir nach langem Überlegen nichts sinnvolles eingefallen. Daher hoffe ich auf eure Hilfe.
Liebe Grüße,
Moe
|
|
| |
|
Hallo und guten Morgen,
gefragt ist bei solcherlei Standardaufgaben zum Thema typischerweise eine mengentheoretische Spezifikation von L(G) -
man nennt das ''in intension'', also zB so:
[mm] L(G)=\{x\in\{a,b\}^{\star}|\:\: n:=|x|\:\: ist\:\: gerade\:\: und\:\: \forall 1\leq i\leq \frac{n}{2}\: x_i=x_{n-i+1}\}
[/mm]
Gruss,
Mathias
|
|
|
|
