Grundlagen der Programmierung (Grammatik Aufgabe)

[ITBEGINNER]

Ich bräuchte mal etwas Hilfe bei diesen Aufgaben. Trotz mehrfachem lesen im Skript und auch das Anschauen verschiedenster YouTube Videos werde ich nicht schlauer, was dieses Thema betrifft.

1. Aufgabe
Seien die folgenden beiden Grammatiken gegeben:

G1 = (N, T, P1, S) und G2 = (N, T, P2, S)

N = {S, B},

T = {a, b, c}und

P1 = {(S,aB), (S,bB), (B,aS), (B,bS), (B,ε)} und
P2 = {(S,aSa), (S,bSb), (S,c)}

(a) Bestimmen Sie mit Hilfe von Beispielen die Sprache L(G1).
(b) Bestimmen Sie mit Hilfe von Beispielen die Sprache L(G2).

 

2. Aufgabe

Seien die folgenden beiden Grammatiken gegeben:

G1 = (N, T, P1, S) und G2 = (N, T, P2, S)
N = {S}, T = {a, b}.
(a) Bestimmen Sie P1 (möglichst minimal) so dass die folgende Sprache erzeugt wird:
Aufgabe

(b) Bestimmen Sie P2 (möglichst minimal) so dass die folgende Sprache erzeugt wird:
Aufgabe

Bearbeitet 30. Oktober 2022 von SlickSii

[eKrumel]

Was sind denn deine Lösungsansätze bisher oder deine Gedanken dazu ? Dann kann man dir auch weiterhelfen.

[Alexej_a7x]

Bei Aufgabe 1 geht es wohl darum festzustellen, welche Sprache vorliegt. Also ob eine reguläre, kontextfreie oder kontextsensitive Sprache vorliegt. Chomskys Hierarchie

 

Bei Aufgabe 2a geht es darum, dass du die Regeln angeben musst, sodass du Wörter wie "aabb", " ab", "aaaabbbb" und so weiter bilden kannst. Das leere Wort ist auch Bestandteil der Sprache. Schau dir P2 aus Aufgabe 1 als "Inspiration" an.

 

Bei Aufgabe 2b geht es darum Wörter wie "abab", " ab" oder "abababab" bilden zu können. Hier gehe ich davon aus, dass das leere Wort nicht Bestandteil der Sprache ist, weil n eine natürliche Zahl sein muss.

 

Vielleicht hilft das schon

 

Edit: 2b natürliche Zahlen ergänzt.

 

 

 

 

Bearbeitet 30. Oktober 2022 von Alexej_a7x
Ergänzung

[ITBEGINNER]

@Alexej_a7x Danke dir, das Ganze hat mir um einiges weiter geholfen. 👍