TI Grammatik angeben < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:39 Mo 09.12.2013 | | Autor: | gsracer |
| Aufgabe | (a)
Geben Sie für [mm] \IN= \{0, 1, 2, 3...\}, [/mm] also der Darstellung der natürlichen Zahlen
inklusive der Null, eine erzeugende Grammatik an, die berücksichtigt, dass es keine
führenden Nullen geben darf.
(b)
In Programmiersprachen spielen Klammerungen bestehend aus Klammerpaaren mit
öffnender und schließender Klammer eine wichtige Rolle (z. B. zum Gruppieren von
Programmelementen). Geben Sie eine Grammatik an, die alle möglichen Klammerungen
über den Klammerpaaren (), <>, [], {},BEGIN END,IF FI erzeugt.
(c)
Geben Sie eine Grammatik an, die die folgende Sprache erzeugt:
L = [mm] \{ w| w\in a, b,c\}\*,w
[/mm]
enthält gleich viele a’s, b’s und c’sg
Von welchem Typ sind die von Ihnen definierten Grammatiken?
Begründen Sie im Folgenden jeweils, warum die von Ihnen erzeugte Grammatik die
jeweilige Sprache erzeugt. |
Hallo,
Ich habe ein Problem:
Ich weiß überhaupt nicht wie ich diese 3 Aufgaben angehen soll.
Kann mir jemand Tipps geben, ich wäre dafür sehr sehr dankbar
Eine Idee zur Aufgabe a) wäre folgende.
Ich kann ja alle möglichen Wörter bilden, nur es darf keine führenden Nullen geben.
Also konkret wäre das z.B.
01230 <------nicht erlaubt
01212301 <----- erlaubt
Jetzt muss ich doch einen Zusammenhang erstellen, also ein Art Muster??
Aufgabe b) stelle ich mir ähnlich vor aber bei Aufgabe c) habe ich keinerlei Ahnung bzw. eine Idee.
Vielen Dank im Voraus
Gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:20 Di 10.12.2013 | | Autor: | Ebri |
> Hallo,
Hi
>
> Ich habe ein Problem:
>
> Ich weiß überhaupt nicht wie ich diese 3 Aufgaben angehen
> soll.
> Kann mir jemand Tipps geben, ich wäre dafür sehr sehr
> dankbar
>
> Eine Idee zur Aufgabe a) wäre folgende.
> Ich kann ja alle möglichen Wörter bilden, nur es darf
> keine führenden Nullen geben.
> Also konkret wäre das z.B.
> 01230 <------nicht erlaubt
> 01212301 <----- erlaubt
> Jetzt muss ich doch einen Zusammenhang erstellen, also ein
> Art Muster??
(a)
So wie ich das verstanden habe soll ich die Grammatik alle natürlichen Zahlen (einschließlich der 0) erzeugen.
D.h. alle Möglichen Kombinationen von {0,1,2,3,4,5,6,7,8,9} =: [mm] \Sigma [/mm] mit der Einschränkung, dass es keine führende 0 geben darf.
> 01230 <------nicht erlaubt
> 01212301 <----- erlaubt
Beides nicht erlaubt, da eine 0 vorne.
Mit [mm] \Sigma [/mm] haben wir schon mal das Alphabet der Terminalsymbole. Fehlen noch die Nonterminale und die Produktionsregeln.
Seien S,R Nonterminale und S das Startsymbol. 0 soll erlaubt sein, aber keine führende 0. Ich mach mal den Anfang:
Produktionsregeln:
S -> 0 | 1R | 2R | ..
R -> ...
...
Bei der ersten Zahl muss man aufpassen. Entweder es kommt eine 0 oder 1,2,3,4,5,6,7,8,9.
War die erste Zahl nicht 0 sind danach alle Möglichen Kombinationen von {0,1,2,3,4,5,6,7,8,9} erlaubt.
> Aufgabe b) stelle ich mir ähnlich vor aber bei Aufgabe c)
> habe ich keinerlei Ahnung bzw. eine Idee.
(b)
Hier bin ich mir nicht ganz sicher wie die erzeuge Sprache aussehen soll. Nur geschachtelt IF<[]>FI oder auch BEGIN{}END[()], ich schätze mal letzteres.
(c)
Knifflig.
Nachtrag:
Überlege dir zuerst eine Grammatik die nur Wörter mit gleich vielen a's, b's, c's erzeugt. Zum Beispiel für (abc)* .
Hat man so eine Grammatik, modifiziert man diese sodass beliebige Vertauschungen der Buchstaben möglich sind.
> Vielen Dank im Voraus
>
> Gruß
Gruß
Ebri
|
|
|
|
