reg. Ausdruck -> NEA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben Sie einen NEA an, der die Sprache des regulären Ausdrucks [mm] $((aa)^{\*} [/mm] + a(a + [mm] b)^{\*}b)^{\*}$ [/mm] akzeptiert. |
Hallo,
ich stehe bei dieser Aufgabe leider total auf der Strecke. Der Satz für die Transformation einer RL Grammatik in einen NEA lautet:
Sei $G = (V, [mm] \Sigma, [/mm] P, S)$ eine RL Grammatik.
Der NEA $A = (Z, [mm] \Sigma, \delta, z_{0,}, [/mm] E)$ sei definiert durch:
$Z = V, [mm] z_{0} [/mm] = S, E = [mm] \{A|A \to \varepsilon \in P\}, \delta [/mm] = [mm] \{A \to_{a} B|A \to aB \in P\}.$
[/mm]
Dann gilt:
[mm] $\mathcal [/mm] L (A) = [mm] \mathcal [/mm] L (G).$
Bei meiner Aufgabe habe ich bis auf den "regulären Ausdruck" aber sonst nichts gegeben und ich weiß außerdem nicht, wie eine Transformation reg. Ausdruck -> NEA genau gehen soll. Es wäre sehr nett, wenn mir jemand etwas Hilfe leisten könnte...
---
EDIT:
Ich glaube ich bin auf den Seiten 24/25 des folgenden Links fündig geworden:
![[]](/images/popup.gif) Link-Text
Täusche ich mich, oder enthält der NEA im Beispiel auf Seite 25 Epsilon-Transitionen (in unserer Vorlesung wurden nämlich NEAs ohne Epsilon-Transitionen definiert, demnach wäre das Beispiel für mich wertlos...)?
---
Vielen Dank für die Mühe!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:11 So 22.05.2011 | | Autor: | felixf |
Moin!
> Geben Sie einen NEA an, der die Sprache des regulären
> Ausdrucks [mm]((aa)^{\*} + a(a + b)^{\*}b)^{\*}[/mm] akzeptiert.
>
> Hallo,
>
> ich stehe bei dieser Aufgabe leider total auf der Strecke.
> Der Satz für die Transformation einer RL Grammatik in
> einen NEA lautet:
>
> Sei [mm]G = (V, \Sigma, P, S)[/mm] eine RL Grammatik.
> Der NEA [mm]A = (Z, \Sigma, \delta, z_{0,}, E)[/mm] sei definiert
> durch:
> [mm]Z = V, z_{0} = S, E = \{A|A \to \varepsilon \in P\}, \delta = \{A \to_{a} B|A \to aB \in P\}.[/mm]
>
> Dann gilt:
> [mm]\mathcal L (A) = \mathcal L (G).[/mm]
>
>
> Bei meiner Aufgabe habe ich bis auf den "regulären
> Ausdruck" aber sonst nichts gegeben und ich weiß außerdem
> nicht, wie eine Transformation reg. Ausdruck -> NEA genau
> gehen soll. Es wäre sehr nett, wenn mir jemand etwas Hilfe
> leisten könnte...
Nun, du hast es ja schon selbst gefunden:
> ---
> EDIT:
>
> Ich glaube ich bin auf den Seiten 24/25 des folgenden Links
> fündig geworden:
>
> Link-Text
genau so geht das. Es gibt ein paar Grundregeln, mit denen du aus jedem RA einen NEA machen kannst.
> Täusche ich mich, oder enthält der NEA im Beispiel auf
> Seite 25 Epsilon-Transitionen (in unserer Vorlesung wurden
> nämlich NEAs ohne Epsilon-Transitionen definiert, demnach
> wäre das Beispiel für mich wertlos...)?
Ja, er hat Epsilon-Transitionen. Alle Kanten ohne Beschriftung sind Epsilon-Transitionen.
Die kannst du allerdings auch alle wieder loswerden, indem du sowas aehnliches wie die "transitive Huelle" bildest.
Wenn du z.B. im Zustand 1 bist und ein a kommt, so kannst du via Epsilon-Transitionen ueber 9 zu 10 gehen. Also zeichnst du einen Pfeil von 1 nach 10 ein und schreibst ein a drueber. Ansonsten kommst du nicht mit Epsilon-Transitionen zu einer a-Transition. Allerdings zu einer b-Transition.
Wenn du alle diese Wege von 1 aus abgeklappert hast, kannst du die beiden in 1 beginnenden Epsilon-Transitionen entfernen. Jetzt suchst du dir einen neuen Zustand, wo eine Epsilon-Transition losgehst, und machst das gleiche. Zum Schluss laesst du alle Zustaende weg, zu denen nichts mehr hingeht. (Wie etwa 2, 5, 7, 9 in diesem Beispiel.)
Schliesslich erhaelst du einen NEA ohne Epsilon-Transition, also nach eurer Definition einen "richtigen" NEA.
LG Felix
|
|
|
| |
|
| Aufgabe | | Geben Sie einen NEA an, der die Sprache des regulären Ausdrucks [mm] $((aa)^{*} [/mm] + a(a + [mm] b)^{*}b)^{*}$ [/mm] akzeptiert. |
Hallo Felix,
> > Ich glaube ich bin auf den Seiten 24/25 des folgenden Links
> > fündig geworden:
> >
> >
> Link-Text
>
> genau so geht das. Es gibt ein paar Grundregeln, mit denen
> du aus jedem RA einen NEA machen kannst.
ich versuche seit einiger Zeit das Beispiel auf Seite 25 nachzuvollziehen, schaffe es aber nicht... Gegeben ist a+(bc)*.
- Warum hat ein Knoten im Syntaxbaum keine Beschriftung?
- So wie ich das verstanden habe, muss ich nun die Regeln von Seite 24 auf den Syntaxbaum anwenden. Wie lautet aber das "Kochrezept" dafür?
Irgendwie ist es merkwürdig, dass ich mit JFLAP (ich denke Du kennst das Programm) eine andere Grafik erhalte als auf Seite 25...
> LG Felix
Ich danke Dir vielmals!
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:21 So 22.05.2011 | | Autor: | felixf |
Moin!
> Geben Sie einen NEA an, der die Sprache des regulären
> Ausdrucks [mm]((aa)^{*} + a(a + b)^{*}b)^{*}[/mm] akzeptiert.
> Hallo Felix,
>
> > > Ich glaube ich bin auf den Seiten 24/25 des folgenden Links
> > > fündig geworden:
> > >
> > >
> >
> Link-Text
>
> >
> > genau so geht das. Es gibt ein paar Grundregeln, mit denen
> > du aus jedem RA einen NEA machen kannst.
>
> ich versuche seit einiger Zeit das Beispiel auf Seite 25
> nachzuvollziehen, schaffe es aber nicht... Gegeben ist
> a+(bc)*.
> - Warum hat ein Knoten im Syntaxbaum keine Beschriftung?
Doch, er hat die Beschriftung "" (das in den Anfuehrungszeichen). Das "" ist der Konkatenationsoperator, wie er in $bc$ zwischen b und c vorkommt :)
> - So wie ich das verstanden habe, muss ich nun die Regeln
> von Seite 24 auf den Syntaxbaum anwenden. Wie lautet aber
> das "Kochrezept" dafür?
Du kannst entweder top-down vorgehen oder bottom-up.
Fangen wir mal unten an. Baue zuerst Automaten fuer a, b, c. Das ist einfach. Dann bau einen Automaten fuer den Konkatenationsoperator. In diesem fuegst du die Automaten fuer b und c ein. Dann baust du den Automaten fuer den Stern-Operator: dort baust du den Automaten vom Konkatenationsoperator ein.
Schliesslich baust du den Automaten fuer den +-Operator, und baust dort die Baeume fuer a und den Stern-Operator ein.
> Irgendwie ist es merkwürdig, dass ich mit JFLAP (ich denke
> Du kennst das Programm) eine andere Grafik erhalte als auf
> Seite 25...
JFLAP kenne ich nicht.
LG Felix
|
|
|
| |
|
| Aufgabe | | Geben Sie einen NEA an, der die Sprache des regulären Ausdrucks [mm] $((aa)^{\*} [/mm] + a(a + [mm] b)^{\*}b)^{\*}$ [/mm] akzeptiert. |
Moin Felix,
> Link-Text
>
> > - Warum hat ein Knoten im Syntaxbaum keine
> Beschriftung?
>
> Doch, er hat die Beschriftung "" (das in den
> Anfuehrungszeichen). Das "" ist der Konkatenationsoperator,
> wie er in [mm]bc[/mm] zwischen b und c vorkommt :)
bevor ich die eigentliche Aufgabe löse, frage ich vorher zur Sicherheit nach: ist es normal, dass die Klammern im Syntaxbaum nicht berücksichtigt werden?
> Du kannst entweder top-down vorgehen oder bottom-up.
>
> Fangen wir mal unten an. Baue zuerst Automaten fuer a, b,
> c. Das ist einfach. Dann bau einen Automaten fuer den
> Konkatenationsoperator. In diesem fuegst du die Automaten
> fuer b und c ein. Dann baust du den Automaten fuer den
> Stern-Operator: dort baust du den Automaten vom
> Konkatenationsoperator ein.
>
> Schliesslich baust du den Automaten fuer den +-Operator,
> und baust dort die Baeume fuer a und den Stern-Operator
> ein.
Super erklärt, jetzt habe ich es endlich kapiert! ![[anbet]](/images/smileys/anbet.gif "[anbet]")
Einzig die Vorgehensweise bei der Nummerierung der Knoten bereitet mir noch etwas Kopfschmerzen... Gibt es da ein System?
> LG Felix
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:56 So 22.05.2011 | | Autor: | felixf |
Moin!
> Geben Sie einen NEA an, der die Sprache des regulären
> Ausdrucks [mm]((aa)^{\*} + a(a + b)^{\*}b)^{\*}[/mm] akzeptiert.
>
> Moin Felix,
>
> >
> Link-Text
>
> >
> > > - Warum hat ein Knoten im Syntaxbaum keine
> > Beschriftung?
> >
> > Doch, er hat die Beschriftung "" (das in den
> > Anfuehrungszeichen). Das "" ist der Konkatenationsoperator,
> > wie er in [mm]bc[/mm] zwischen b und c vorkommt :)
>
> bevor ich die eigentliche Aufgabe löse, frage ich vorher
> zur Sicherheit nach: ist es normal, dass die Klammern im
> Syntaxbaum nicht berücksichtigt werden?
Jein.
Die Klammern geben an, wie genau der Syntaxbaum aussieht, z.B. geben $(a b) c$ und $a (b c)$ zwei verschiedene Baeume.
Im Baum selber kommen die Klammern aber nicht mehr vor.
> > Du kannst entweder top-down vorgehen oder bottom-up.
> >
> > Fangen wir mal unten an. Baue zuerst Automaten fuer a, b,
> > c. Das ist einfach. Dann bau einen Automaten fuer den
> > Konkatenationsoperator. In diesem fuegst du die Automaten
> > fuer b und c ein. Dann baust du den Automaten fuer den
> > Stern-Operator: dort baust du den Automaten vom
> > Konkatenationsoperator ein.
> >
> > Schliesslich baust du den Automaten fuer den +-Operator,
> > und baust dort die Baeume fuer a und den Stern-Operator
> > ein.
>
> Super erklärt, jetzt habe ich es endlich kapiert!
> Einzig die Vorgehensweise bei der Nummerierung der Knoten
> bereitet mir noch etwas Kopfschmerzen... Gibt es da ein
> System?
Die Nummerierung ist voellig egal. Du kannst die Zustaende nennen wie du willst.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Di 24.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:25 Di 24.05.2011 | | Autor: | el_grecco |
Hallo,
ich brauche leider noch nachwievor Hilfe bei den Punkten aus meinem letzten Beitrag.
Es wäre sehr nett, wenn sich jemand bei Gelegenheit und Motivation (hey, ich weiß, dass das Wetter im Moment verdammt gut ist  ) das kurz ansehen könnte.
Auf jeden Fall: vielen Dank!
Gruß
el_grecco
|
|
|
|
![[]](http://img695.imageshack.us/img695/949/aufgabe.jpg){kind=small}
Aufgabe![[]](http://img222.imageshack.us/img222/7793/beispielo.jpg){kind=small}
Beispiel