 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Philipp Janda
Guest
|
 Posted: Thu Dec 18, 2003 2:25 pm Post subject: Potenzmengen als DFA-Zustaende |
 |
|
Moin *!
Ich will momentan die Kurve von Regular Expressions ueber NFAs zu DFAs
in C++ implementieren. Als Zustaende reichen mir eigentlich ganze Zahlen
(brauch ich spaeter sowieso), aber beim Uebergang von NFA zu DFA brauche
ich fuer die ueblichen Algorithmen Potenzmengen von Zustaenden.
Ich weiss jetzt nicht so genau, wie ich diese Potenzmengen-Zustaende in
C++ repraesentieren kann.
Einzige Idee waere std::set, aber es kommt mir so verschwenderisch vor,
fuer jeden Zustand eine eigene set zu erzeugen (vor allem, weil die
Anzahl der Zustaende von NFA zu DFA drastisch zunehmen koennte).
Hat jemand eine bessere Idee?
Und wie machen das eigentlich die C-Leute (die haben ja keine std::set)?
Gruesse,
Philipp
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
 |
Gerhard Wesp
Guest
|
| Posted: Fri Dec 19, 2003 9:02 am Post subject: Re: Potenzmengen als DFA-Zustaende |
|
|
Philipp Janda <siffiejoe (AT) gmx (DOT) net> wrote:
| Quote: | Einzige Idee waere std::set, aber es kommt mir so verschwenderisch vor,
fuer jeden Zustand eine eigene set zu erzeugen (vor allem, weil die
Anzahl der Zustaende von NFA zu DFA drastisch zunehmen koennte).
|
NFA, DFA's ist eine Weile her bei mir. Aber wenn du eine Menge
brauchst, brauchst du eine Menge, und dann ist std::set ``The way to
go''.
| Quote: | Und wie machen das eigentlich die C-Leute (die haben ja keine std::set)?
|
Wenn sie eine Menge brauchen, implementieren sie sie selber. Des
oefteren suboptimal (evtl. als Liste, ``ich hab sowieso nie mehr als 10
Elemente''). Und fuer jeden Elementtyp einzeln.
-Gerhard
--
| Quote: | voice: +43 (0)662 642934 *** web: http://www.cosy.sbg.ac.at/~gwesp/
If emailing to [email]gwesp (AT) cosy (DOT) sbg.ac.at[/email] doesn't work, please try [email]gcw (AT) gmx (DOT) at[/email]!
|
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Andreas Kabel
Guest
|
| Posted: Fri Dec 19, 2003 5:16 pm Post subject: Re: Potenzmengen als DFA-Zustaende |
|
|
Philipp Janda <siffiejoe (AT) gmx (DOT) net> writes:
| Quote: | Moin *!
Ich will momentan die Kurve von Regular Expressions ueber NFAs zu DFAs
in C++ implementieren. Als Zustaende reichen mir eigentlich ganze Zahlen
(brauch ich spaeter sowieso), aber beim Uebergang von NFA zu DFA brauche
ich fuer die ueblichen Algorithmen Potenzmengen von Zustaenden.
|
Die Nomenklatur scheint mir nicht ganz richtig. Als Zustandselemente
des DFA braucht man Mengen von NFA-Zustaenden. Die Zustandsmenge des
DFA ist also eine Untermenge der Potenzmenge der Menge der
NFA-Zustaende.
| Quote: | Ich weiss jetzt nicht so genau, wie ich diese Potenzmengen-Zustaende in
C++ repraesentieren kann.
Einzige Idee waere std::set, aber es kommt mir so verschwenderisch vor,
fuer jeden Zustand eine eigene set zu erzeugen (vor allem, weil die
Anzahl der Zustaende von NFA zu DFA drastisch zunehmen koennte).
Hat jemand eine bessere Idee?
|
Eventuell Bitstrings, wenn die Anzahl der NFA-Zustaende ueberschaubar
ist. Natuerlich sollte man keine ::std::set<int> benutzen, um die
DFA-Zustaende zu numerieren, da wuerde ich eine Liste anlegen und
mit Indizes operieren.
| Quote: | Und wie machen das eigentlich die C-Leute (die haben ja keine std::set)?
|
Bitstrings.
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Thorsten Nitz
Guest
|
| Posted: Fri Dec 26, 2003 7:19 pm Post subject: Re: Potenzmengen als DFA-Zustaende |
|
|
Philipp Janda wrote:
| Quote: | Ich will momentan die Kurve von Regular Expressions ueber NFAs zu DFAs
in C++ implementieren. Als Zustaende reichen mir eigentlich ganze Zahlen
(brauch ich spaeter sowieso), aber beim Uebergang von NFA zu DFA brauche
ich fuer die ueblichen Algorithmen Potenzmengen von Zustaenden.
Ich weiss jetzt nicht so genau, wie ich diese Potenzmengen-Zustaende in
C++ repraesentieren kann.
|
Zustandsautomaten können durch Tabellen repräsentiert werden. Erste Idee
für Tabellen ist immer std::vector.
Ein Automat hat Zustände, die eine Zuordnungstabelle enthalten, die zu
jeder Eingabe einen Nachfolgezustand enthalten. Du sagt, Dir würden ints
reichen. Nehmen wir also an, die Eingaben des Automaten seien als ints
darstellbar und die Zustände würden auch einfach durchnummeriert.
class Zustand {
std::vector <int> zustand;
public:
int zustandZuEingabe(int eingabe)
{ return zustand.at(eingabe);
}
// Fehlen noch Methoden zum Füllen, Kopieren usw.
};
Hier wird die Eingabe direkt als Index in einen Vektor benutzt. D.h.,
die möglichen Eingaben sollten einen Bereich von 0 ... N möglichst dicht
belegen. Für jede mögliche Eingabe (und wenn es im Bereich 0 ... N
Lücken gibt, auch für die Lücken) wird ein Eintrag im Vektor benutzt.
Wenn der Definitionsbereich der Eingaben nicht dicht ist, kannst Du den
std::vector gegen ein std::set austauschen. In der Zugfiffsmethode
zustandZuEingabe musst Du statt std::vector::at() nun std::set::find()
benutzen und den Fall, dass zur Eingabe kein Eintrag vorhanden ist,
behandeln.
Der gesamte Automat besteht aus einer Tabelle aller seiner Zustände
sowie einem Merker, welcher Zustand gerade eingenommen wird.
class Automat {
std::vector< Zustand> zustaende;
int aktZustand;
public:
int eingabe(int e) {
aktZustand = zustaende[aktZustand].zustandZuEingabe(e);
return aktZustand;
}
// Fehlen noch Methoden zum Füllen, Kopieren usw.
};
Die Zustände kannst Du beliebig nummerieren, also insbesondere auch
fortlaufend, daher sehe ich hier keine Notwendigkeit, mit einem Set zu
arbeiten. Solltest Du den Zuständen hingegen Namen geben wollen und dann
bevorzugt über die Namen zugreifen, käme ein std::set in Frage.
| Quote: | Einzige Idee waere std::set, aber es kommt mir so verschwenderisch vor,
fuer jeden Zustand eine eigene set zu erzeugen []
|
An einem set ist nichts verschwenderisch. Im obigen Beispiel belegt
jeder Eintrag in Zustand::zustand ein int. Wenn Du statt std::vector ein
std::set nimmst, verursachen Lücken im Definitionsbereich keine
Einträge. Wenn Du dem vector oder set vor dem Füllen mit reserve
mitteilst, wieviele Einträge kommen, wird auch der Speicher passend
alloziert.
Überhaupt konzentrieren sich die Platzspar-Überlegungen auf die Klasse
Zustand. Ein Exemplar dieser Klasse belegt immer soviele Einträge, wie
der jeweilige Zustand an Eingaben akzeptiert. D.h., ein Zustand, der nur
eine Eingabe akzeptiert, verbraucht nach obigem Vorschlag auch nur Platz
für ein int. Was das obige Konzept noch nicht leistet, ist die
Behandlung von Bereichen: Z.B. sollen die Eingaben 3,4,5,6 alle auf den
selben Folgezustand, z.b. 4711 führen. Hier müssten vier Einträge
angelegt werden. Man könnte über eine kompaktere Darstellung nachdenken,
die nur die Zahlen (3,5,4711) sowie eine Kennung "Intervall" speichert.
Viel Spaß beim Ausarbeiten.
| Quote: | Und wie machen das eigentlich die C-Leute (die haben ja keine std::set)?
|
Alles von Hand coden. Wenn Du Dir den Code anschaust, den z.B. flex
erzeugt, siehst Du, dass der Automat als zweidimensionales Array
abgelegt wird. Wenn Du sowas von Hand debuggen musst, wirst Du
wahnsinnig. Der Vorteil von flex et al. ist, dass das Werkzeug Dir die
Tabellen aufbaut und für die Richtigkeit garantiert.
Tschö, wa!
Thorsten
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
Thorsten Nitz
Guest
|
| Posted: Sat Dec 27, 2003 12:58 pm Post subject: Re: Potenzmengen als DFA-Zustaende |
|
|
Philipp Janda wrote:
[Automaten implementieren]
| Quote: | Einzige Idee waere std::set,
|
Hier ist die Stelle, an der ich im meinem vorigen Posting der falschen
Fährte gefolgt bin. Leider ist es nun zum Canceln zu spät.
Du brauchst eine Abbildung von der Menge der Eingaben auf die Menge der
Zustände. Ein Set hilft Dir nicht wirklich weiter; Abbildungen
implementiert man mit std::map:
class Zustand {
// Übergänge aus diesem Zustand
std::map< EingabeTyp, ZustandTyp> zustandZuEingabe;
public:
// Alle möglichen Methoden
};
| Quote: | aber es kommt mir so verschwenderisch vor,
fuer jeden Zustand eine eigene set zu erzeugen (vor allem, weil die
Anzahl der Zustaende von NFA zu DFA drastisch zunehmen koennte).
|
Nach Deinen Angaben wären EingabeTyp und ZustandTyp beide int. Damit
belegt jeder Übergang Platz für zwei ints. In der im anderen Posting
vorgestellten Methode mit std::vector brauchst Du nur Platz für ein int
pro Übergang, musst allerdings eventuell Leereinträge in Kauf nehmen.
Der Grund-Speicherbedarf für eine Map ist recht gering. Auf meiner
Plattform ergibt sizeof( std::map<int, int> ) den Wert 16 (ein Zeiger
auf das erste Element im Baum, ein Zeiger auf die Vergleichsfunktion).
Dazu kommt dann noch der Platz für die Einträge.
Auf der anderen Seite frage ich mich, was Du als "drastische Anzahl"
ansiehst. Eingaben hast Du wohl höchstens 256 verschiedene. Wenn Dein
Automat 1000 Zustände hat, sind das je Zustand 256* 2 * sizeof int +
sizeof std::map, auf meiner Plattform also z.B. 4112 Byte. Das mal 1000
Zustände gibt 4,1 Millionen Byte. Nimmst Du short statt int, halbiert
sich das. Zeitgenössische Rechner bewältigen solche Datenmengen ohne
Probleme.
Tschö, wa!
Thorsten
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
