|
Community
Szene & News
Locations
Impressum
|
Forum / Sonstiges
Theoretische informatik
defg  - 37
Fortgeschrittener
(offline)
Dabei seit 09.2007
32
Beiträge
|
|
Geschrieben am: 02.02.2009 um 15:10 Uhr
|
|
Hallo kann mir mal bitte jemand helfen, ich schreib bald eine Theoretische Informatik klausur und ich weiß nicht weiter:
Das thema lauter Grammatik oder kontextfreie Gramatik!
Was ist der Unterschied zwischen {a,b} und {a,b}* ?
bitte erklärt es mir mit hilfe eines beispiels.
|
|
RoHaN - 45
Profi
(offline)
Dabei seit 04.2006
698
Beiträge
|
|
Geschrieben am: 02.02.2009 um 15:19 Uhr
|
|
oje du armer Hund 
ich hab das zum Glück hinter mir, ich hab mir das zwar irgendwo mal aufgeschrieben finds aber grad net wenns mir wieder eifällt sag ich dir bescheid
Alcohol doesn't solve any problems, but if you think again, neither does Milk !!!
|
|
Variable - 38
Anfänger
(offline)
Dabei seit 06.2005
2
Beiträge
|
Geschrieben am: 02.02.2009 um 15:35 Uhr
Zuletzt editiert am: 02.02.2009 um 15:42 Uhr
|
|
Soweit ich weiß bedeutet das * (Sternchen) "beliebig oft". Sprich du kannst (wo auch immer?) das Pärchen {a,b} beliebig oft verwenden. Im Gegensatz zu {a,b} ohne Sternchen, wo das Pärchen a,b nur einmal verwendet werden darf.
Zitat:
(a)*, d.h. die durch den regulären Ausdruck a definierte Zeichenkette kann beliebig oft (auch 0-mal) hintereinander vorkommen
// Edit: Oh da war wohl jemand schneller 
|
|
Interior - 41 
Team-Ulmler
(offline)
Dabei seit 08.2002
1274
Beiträge
|
|
Geschrieben am: 02.02.2009 um 15:36 Uhr
|
|
Zitat von defg: Das thema lauter Grammatik oder kontextfreie Gramatik!
Was ist der Unterschied zwischen {a,b} und {a,b}* ?
Alle endlichen Sprachen sind durch reguläre Ausdrücke beschreibbar. Und das sind eben zwei reguläre Ausdrücke. Beim ersten kommt nur a oder b vor, beim zweiten a oder b beliebig oft (oder gar nicht).
|
|
defg - 37
Fortgeschrittener
(offline)
Dabei seit 09.2007
32
Beiträge
|
|
Geschrieben am: 02.02.2009 um 16:41 Uhr
|
|
gut sind es bei {a,b} die möglichkeiten ? a, b, aa, ab, ba,bb ?
und wie sieht des dann bei {a,b}* aus?..
irgendwie blick ich des no net richtig..
|
|
Fuce - 37
Profi
(offline)
Dabei seit 09.2004
815
Beiträge
|
|
Geschrieben am: 02.02.2009 um 17:41 Uhr
|
|
Zitat von defg: gut sind es bei {a,b} die möglichkeiten ? a, b, aa, ab, ba,bb ?
und wie sieht des dann bei {a,b}* aus?..
irgendwie blick ich des no net richtig..
kannst du net mehr Angaben reinschreiben ? das wird wohl nicht die Definition deiner Grammatik sein ...
IT`S NOT ABOUT BREAKING HEARTS - IT`S ABOUT BREAKING FACES !
|
|
tanz-gott - 31
Halbprofi
(offline)
Dabei seit 05.2008
338
Beiträge
|
|
Geschrieben am: 02.02.2009 um 17:42 Uhr
|
|
Zitat von defg: gut sind es bei {a,b} die möglichkeiten ? a, b, aa, ab, ba,bb ?
und wie sieht des dann bei {a,b}* aus?..
irgendwie blick ich des no net richtig..
bei {a,b} kannst du eben nur eine der von dir aufgezählten möglichkeiten verwenden, bei {a,b}* kannst du alle so oft du willst verwenden, oder eben gar nicht
neues profil hier---->http://www.team-ulm.de/Profi l/589914
|
|
defg - 37
Fortgeschrittener
(offline)
Dabei seit 09.2007
32
Beiträge
|
|
Geschrieben am: 02.02.2009 um 18:35 Uhr
|
|
Ich schreib euch jetzt mal einfach eine Aufgabe rein:
Geben sie eine kontextfreie Grammatik g an, die genau die Polidrome über {0,1} erzeugt.
Lösung:
G({s},{0,1},P,S}
P={S->0|1|00|11|0S0|1S}
die Lösung würde doch stimmen wenn des {0,1}* heißen würde oder?... wenn es nur {0,1} heißt lautet die lösung 0|1|00|11 , wenn man nur eines verwenden darf!?
|
|
SomeHow - 35
Halbprofi
(offline)
Dabei seit 05.2005
280
Beiträge
|
|
Geschrieben am: 02.02.2009 um 19:18 Uhr
|
|
Zitat von defg: Ich schreib euch jetzt mal einfach eine Aufgabe rein:
Geben sie eine kontextfreie Grammatik g an, die genau die Polidrome über {0,1} erzeugt.
Lösung:
G({s},{0,1},P,S}
P={S->0|1|00|11|0S0|1S}
die Lösung würde doch stimmen wenn des {0,1}* heißen würde oder?... wenn es nur {0,1} heißt lautet die lösung 0|1|00|11 , wenn man nur eines verwenden darf!?
du verwechselst 2 verschiedene sachen
die EBNF und die normale Grammatik
bei der EBNF gibts zB n + und n * über den klammern bei einer grammatik darf es nicht vorkommen
|
|
SomeHow - 35
Halbprofi
(offline)
Dabei seit 05.2005
280
Beiträge
|
|
Geschrieben am: 02.02.2009 um 19:20 Uhr
|
|
http://de.wikipedia.org/wiki/Kontextfreie_Grammatik
http://de.wikipedia.org/wiki/Erweiterte_Backus-Naur_Form
das les das mal hier durch sollte helfen
|
|
Lizardo - 37
Anfänger
(offline)
Dabei seit 03.2005
19
Beiträge
|
Geschrieben am: 03.02.2009 um 00:17 Uhr
Zuletzt editiert am: 03.02.2009 um 00:20 Uhr
|
|
Zitat von defg: Ich schreib euch jetzt mal einfach eine Aufgabe rein:
Geben sie eine kontextfreie Grammatik g an, die genau die Polidrome über {0,1} erzeugt.
Lösung:
G({s},{0,1},P,S}
P={S->0|1|00|11|0S0|1S}
die Lösung würde doch stimmen wenn des {0,1}* heißen würde oder?... wenn es nur {0,1} heißt lautet die lösung 0|1|00|11 , wenn man nur eines verwenden darf!?
Um die Aufgabe zu lösen müsstest du erstmal wissen was Polidrome sein sollen. Da ich davon aber noch nie etwas gehört habe und es von den Produktionsregeln her stark an Palindrome erinnert, gehe ich mal davon aus, dass genau diese gemeint sind. In der Aufgabe geht es darum eine Grammatik zu schreiben die genau die Palindrome bestehend aus 1en und 0en erzeugt. Palindrome wären hier z.B. 0, 1, 00, 11, 101, 010, 1001, 0110 wie du siehst ist ein Muster zu erkennen. Wenn du nämlich diese Wörter in genau 2 gleich lange Teilwörter zerlegst wirst du feststellen dass das eine das Spiegelbild des anderen ist. Im Falle dass das Wort eine ungerade Länge hat wird das Zeichen in der Mitte ignoriert, es kann hier also entweder eine 1 oder eine 0 stehen. Wenn du genaueres über Palindrome erfahren willst kannst du ja bei Wikipedia nachschauen.
Mit diesem Wissen kommt man auf die Produktionsregeln S->0 | 1 | 00 | 11 | 0S0 | 1S1.
Unter Verwendung des leeren Wortes kannst du dir sogar eine Regel sparen. Das würde dann wie folgt aussehen: S->€ | 0 | 1 | 0S0 | 1S1.
Wobei € für das leere Wort steht. Um nochmal auf deine Frage zurückzukommen: die geschweiften Klammern geben an dass es sich um eine Menge handelt. In dieser Aufgabe: die Menge der Terminalsymbole.
|
|
Forum / Sonstiges
|
[