Typ einer Grammatik & Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:42 Mi 25.08.2010 | | Autor: | sebid |
| Aufgabe | Sei G := ({S,A,B},{a,b},P,S)
mit
P:={ S → AB, A → aAa|a, B → bBb|b}.
a) Von welchem Typ ist die Grammatik G?
b) Von welchem Typ ist die Sprache L(G)?
Begründen Sie Ihre Antworten! |
Die Grammatik muss doch vom Typ 2 sein, da u [mm] \in [/mm] V und |u| [mm] \le [/mm] |v|.
Kann nicht vom Typ 3 sein, da auf der rechten Seite nicht nur ein einzelnes Terminalzeichen oder Terminalzeichen plus Variable steht.
Reicht das als Begründung?
Zu b)
Da weiß ich gar nicht wie ich das machen soll. Muss die Sprache nicht auch von Typ 2 sein, wenn die Grammatik von Typ 2 ist?
Danke!
Viele Grüße,
Sebastian
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:36 Mi 25.08.2010 | | Autor: | felixf |
Moin Sebastian!
> Sei G := ({S,A,B},{a,b},P,S)
> mit
> P:={ S → AB, A → aAa|a, B → bBb|b}.
>
> a) Von welchem Typ ist die Grammatik G?
> b) Von welchem Typ ist die Sprache L(G)?
>
> Begründen Sie Ihre Antworten!
> Die Grammatik muss doch vom Typ 2 sein, da u [mm]\in[/mm] V und |u|
> [mm]\le[/mm] |v|.
Wenn du mit Typ 2 den entsprechenden Typ aus der Chomsky-Hierarchie meinst (also kontextfrei), dann ja.
Es ist allerdings nicht klar, was du mit "da $u [mm] \in [/mm] V$ und $|u| [mm] \le [/mm] |v|$." meinst. Ich vermute, du beziehst dich auf irgendetwas aus eurer Vorlesung...
> Kann nicht vom Typ 3 sein, da auf der rechten Seite nicht
> nur ein einzelnes Terminalzeichen oder Terminalzeichen plus
> Variable steht.
Genau.
> Reicht das als Begründung?
Vermutlich.
> Zu b)
> Da weiß ich gar nicht wie ich das machen soll. Muss die
> Sprache nicht auch von Typ 2 sein, wenn die Grammatik von
> Typ 2 ist?
Nun, es kann sein dass die Sprache selber z.B. vom Typ 3 ist. Typ-2-Grammatiken erzeugen Sprachen von Typ 2 oder 3.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:33 Do 26.08.2010 | | Autor: | sebid |
Hallo,
> Wenn du mit Typ 2 den entsprechenden Typ aus der
> Chomsky-Hierarchie meinst (also kontextfrei), dann ja.
Ja, genau den Typ mein ich.
> Es ist allerdings nicht klar, was du mit "da [mm]u \in V[/mm] und
> [mm]|u| \le |v|[/mm]." meinst. Ich vermute, du beziehst dich auf
> irgendetwas aus eurer Vorlesung…
Stimmt. Ist so nicht verständlich.
Damit war gemeint:
…ist vom Typ 2 falls für alle ihre Regeln u → v gilt, dass u eine einzelne Variable ist (d. h. u [mm] \in [/mm] V ) und |u| [mm] \le [/mm] |v| soll heißen, dass es keine verkürzenden Regeln gibt.
> > Zu b)
> Nun, es kann sein dass die Sprache selber z.B. vom Typ 3
> ist. Typ-2-Grammatiken erzeugen Sprachen von Typ 2 oder 3.
Und wie stell ich das nun fest ob Typ 2 oder 3?
Viele Grüße,
Sebastian
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:30 Do 26.08.2010 | | Autor: | felixf |
Moin!
> > > Zu b)
> > Nun, es kann sein dass die Sprache selber z.B. vom Typ 3
> > ist. Typ-2-Grammatiken erzeugen Sprachen von Typ 2 oder 3.
> Und wie stell ich das nun fest ob Typ 2 oder 3?
Ueberleg dir mal wie genau die Sprache aussieht. Man kann sie sehr einfach beschreiben.
Wenn du keine Idee hast, schreib doch mal einen Haufen Woerter hin, die aus der Sprache sind, und ueberleg dir wie du sie alle zusammen moeglichst einfach beschreiben kannst.
Und schliesslich :Was musst du angeben um zu zeigen, dass es eine Typ-3-Sprache ist?
LG Felix
|
|
|
|
