| Autor |
Beitrag |
    
Georg
| | Veröffentlicht am Donnerstag, den 01. Februar, 2001 - 05:18: | 
|
geg. zwei reguläre Sprachen in Form einer regulären Grammatik
z.b.:
G1: S>aA A>aA A>b
G2: S>bA A>bA A>b
nun habe ich das Problem den Durchschnitt der beiden Sprachen zu bestimmen. A>b kommt in beiden Sprachen vor und wäre somit der Durchschnitt wenn ich die Regeln als Menge betrachten würde. Aber die Regeln kann ich ja auch mit anderen Buchstaben versehen, bei denen sich die Sprache nicht verändert. Wie komme ich nun zum Durchschnitt der beiden Sprachen?
Wie wäre das bei der Vereinigung, das ist ja im Prinzip ähnlich, oder? |
Wm_Markus (Wm_Markus)
| | Veröffentlicht am Donnerstag, den 01. Februar, 2001 - 12:48: |
|
Ganz allgemein gesehen ist der Durchschnitt immer
die gemeinsame Menge aller beteiligten Elemente.
Im Beispiel gilt das tatsächlich für A>b. Wenn man
beweisen kann, daß a=b ist würde der Durchschnitt beider Sprachen tatsächlich aus beiden Sprachen
bestehen (man sieht aber nur eine Menge).
Bei einer Vereinigung werden alle Elemente der beteiligten Mengen addiert und doppelte Elemente
nicht mitgezählt.
WM_ichhoffedashilft Markus |
sebp
| | Veröffentlicht am Montag, den 05. Februar, 2001 - 16:35: |
|
Lieber Georg
Wenn Du den Durchschnitt der beiden Sprachen bestimmen willst, kommst Du am besten, wenn Du erstmal ein paar Wörter aus Deinen Grammatiken ableitest. Dabei wirst Du erkennen, daß a^+ b
(soll heißen a hoch + konkat. b) ein regulärer Ausdruck für G1 und bb^+ ein reg. A. für G2 ist. Aus G2 lassen sich also nur Wörter bilden, die überhaupt kein a enthalten und aus G1 nur Wörter die mind. ein a enthalten. Also ist der Durchschnitt der beiden Sprachen leer. |
|
