Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » Endlicher Automat

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
25.03.2005, 16:58 Uhr
rejo



Hallo Leute!

Könnt ihr mir vielleicht etwas helfen und mir ein paar Ideen geben wie eine Datenstruktur für nen endlichen Automaten aussieht?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
25.03.2005, 19:31 Uhr
0xdeadbeef
Gott
(Operator)


Etwas in der Art:

C++:
class zustand {
  // identifiziert einen Zustand
};

template <typename symbol_t>
class zustandsuebergang_fktor {
public:
  // Übergangsfunktion
  zustand operator()(zustand const &, symbol_t const &) const;
};

template <typename symbol_t,
          typename funktor_t = zustandsuebergangs_fktor<symbol_t> >
class automat {
public:
  template<typename iterator_t>
  bool accepts(iterator_t const &begin, iterator_t const &end) const;

private:
  std::vector<symbol_t> alphabet;
  std::vector<zustand > zustandsmenge;
  std::vector<zustand > finalzustaende;
  funktor_t f;
};


--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
25.03.2005, 20:23 Uhr
rejo



Danke für diesen Ansatz, bitte postet mir noch einige Ideen!
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
25.03.2005, 20:42 Uhr
0xdeadbeef
Gott
(Operator)


Ich fänds ehrlich gesagt sinnvoller, wenn du dir selbst ein paar Gedanken machen würdest, zu denen wir dann unsere Meinung äußern können...
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 25.03.2005 um 20:43 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
28.03.2005, 22:12 Uhr
rejo



Hallo Leute!
Meld mich mal wieder

Ich hab mir einiges überlegt und angefangen diesen code zu schreiben ... der irgendwie nicht so funktioniert wie ich will ^^

Naja wäre nett wenn ihr mir paar Tipps geben könntet


C++:
#ifndef _AUTOMAT_
#define _AUTOMAT_
#include <iostream>
#define ZUSTAND 15
#define NONTSYM 5

struct NEA
{
    int zustand[ZUSTAND];
};

struct DEA
{
    int zustand;
};

struct TMP
{
    int zustand[ZUSTAND];
};

struct Array
{
    int Tab[ZUSTAND];
};

class Automat
{
    private:

        struct NEA NEAtab[ZUSTAND][NONTSYM];
        struct DEA DEAtab[ZUSTAND][NONTSYM];
        struct TMP TMPtab[ZUSTAND][NONTSYM];

        int NEAende[ZUSTAND];
        int DEAende[ZUSTAND];
        int TMPende[ZUSTAND];

    public:

        Automat(void);
        ~Automat(void) { }

        void setNEAtab(struct NEA[ZUSTAND][NONTSYM], int[ZUSTAND]);
        struct NEA getNEAtab(void);

        struct DEA getDEAtab(void);

        friend std::ostream& operator<<(std::ostream&, const Automat&);
        friend std::istream& operator>>(std::istream&, Automat&);

        bool determinisieren(void);
        struct Array nimmZustand(int, int);

        bool syntaxcheck(char*);

        void show(void);
};

#endif




C++:
#include "Automat.h"
#include <iostream>

using namespace std;

Automat::Automat(void)
{
    for(int m = 0; m < ZUSTAND; m++)
    {
        NEAende[m]= DEAende[m] = TMPende[m] = -1;

        for(int n = 0; n < NONTSYM; n++)
        {
            for(int o = 0; o < ZUSTAND; o++)
            {
                DEAtab[m][n].zustand = -1;
                TMPtab[m][n].zustand[o] = -1;
                NEAtab[m][n].zustand[o] = -1;
            }
        }
    }
}

void Automat::setNEAtab(struct NEA tab[ZUSTAND][NONTSYM], int Nende[ZUSTAND])
{
    for(int m = 0; m < ZUSTAND; m++)
    {
        NEAende[m] = Nende[m];
        DEAende[m] = TMPende[m] = -1;

        for(int n = 0; n < NONTSYM; n++)
        {
            for(int o = 0; o < ZUSTAND; o++)
            {
                DEAtab[m][n].zustand = -1;
                TMPtab[m][n].zustand[o] = -1;
                NEAtab[m][n].zustand[o] = tab[m][n].zustand[o];
            }
        }
    }
}

struct NEA Automat::getNEAtab(void)
{
    return NEAtab[ZUSTAND][NONTSYM];
}

struct DEA Automat::getDEAtab(void)
{
    return DEAtab[ZUSTAND][NONTSYM];
}

ostream& operator<<(ostream &o, const Automat &a)
{
    // Ausgabe

    return o;
}

istream& operator>>(istream &i, Automat &a)
{
    // Eingabe

    return i;
}

bool Automat::determinisieren(void)
{
    for(int i = 0; i < NONTSYM; i++)
    {
        for(int j = 0; j < ZUSTAND; j++)
        {
            TMPtab[0][i].zustand[j] = NEAtab[0][i].zustand[j];
        }
    }

    Array a;

    for(int m = 0; m < ZUSTAND; m++)
    {
        for(int n = 0; n < NONTSYM; n++)
        {
            a = nimmZustand(m,n);
            memcpy(TMPtab[m+1][n].zustand, a.Tab, ZUSTAND);
        }
    }

    return false;
}

struct Array Automat::nimmZustand(int x, int y)
{
    Array c;
    int counter = 0;

    for(int b = 0; b < ZUSTAND; b++)
        c.Tab[b] = -1;

    for(int j = 0; j < ZUSTAND; j++)
    {
        for(int k = 0; k < ZUSTAND; k++)
        {
            if(k == TMPtab[x][y].zustand[j])
            {
                for(int a = 0; a < ZUSTAND && NEAtab[k][y].zustand[a] != -1; a++)
                {
                    c.Tab[counter] = NEAtab[k][y].zustand[a];
                    counter++;
                }
            }
        }
    }
    return c;
}

bool Automat::syntaxcheck(char *wort)
{
    // Syntaxcheck

    return false;
}

void Automat::show(void)
{
    for(int x = 0; x < ZUSTAND; x++)
    {
        for(int y = 0; y < NONTSYM; y++)
        {
            for(int z = 0; z < ZUSTAND; z++)
            {
                if(TMPtab[x][y].zustand[z] != -1)
                    cout << TMPtab[x][y].zustand[z];
            }

            cout << "  ";
        }
        cout << "\n";
    }
}




C++:
#include "Automat.h"

int main(void)
{
    struct NEA Tabelle[ZUSTAND][NONTSYM];
    int N_ende[ZUSTAND];
    
    for(int i = 0; i < ZUSTAND; i++)
        for(int x = 0; x < NONTSYM; x++)
            for(int y = 0; y < ZUSTAND; y++)
                Tabelle[i][x].zustand[y] = -1;

    Tabelle[0][0].zustand[0] = 0;        Tabelle[0][0].zustand[1] = 1;
    Tabelle[0][1].zustand[0] = 0;

    Tabelle[1][0].zustand[0] = 2;
    
    Tabelle[2][0].zustand[0] = 3;

    Tabelle[3][1].zustand[0] = 5;

    Tabelle[4][0].zustand[0] = 4;        Tabelle[4][0].zustand[1] = 5;

    Tabelle[4][1].zustand[0] = 5;

    Tabelle[5][0].zustand[0] = 6;

    N_ende[0] = 3;
    N_ende[1] = 6;

    Automat a;

    a.setNEAtab(Tabelle,N_ende);
    a.determinisieren();
    a.show();
    return 0;
}



Ich denk mal ihr seht eh schon das ich noch garnicht am ende des quellcodes bin...
Also bitte postet mir paar Tipps

lg
rejo
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
29.03.2005, 11:01 Uhr
rejo



Guten Morgen

Könnte eigentlich bei memcpy ein fehler passieren sodass er was falsches kopiert?
Passiert nämlich bei diesem code und versteh diesen fehler nicht...

vor dem kopieren

C++:
TMPtab[bla][bla].zustand[0] = -1;
TMPtab[bla][bla].zustand[1] = -1;
TMPtab[bla][bla].zustand[2] = -1;
TMPtab[bla][bla].zustand[3] = -1;
TMPtab[bla][bla].zustand[4] = -1;
TMPtab[bla][bla].zustand[5] = -1;
TMPtab[bla][bla].zustand[6] = -1;
TMPtab[bla][bla].zustand[7] = -1;
TMPtab[bla][bla].zustand[8] = -1;
TMPtab[bla][bla].zustand[9] = -1;
TMPtab[bla][bla].zustand[10] = -1;
TMPtab[bla][bla].zustand[11] = -1;
TMPtab[bla][bla].zustand[12] = -1;
TMPtab[bla][bla].zustand[13] = -1;
TMPtab[bla][bla].zustand[14] = -1;



vor dem kopieren

C++:
a.Tab[0] = 0;
a.Tab[1] = 1;
a.Tab[2] = 2;
a.Tab[3] = 3;
a.Tab[4] = -1;
a.Tab[5] = -1;
a.Tab[6] = -1;
a.Tab[7] = -1;
a.Tab[8] = -1;
a.Tab[9] = -1;
a.Tab[10] = -1;
a.Tab[11] = -1;
a.Tab[12] = -1;
a.Tab[13] = -1;
a.Tab[14] = -1;



nach memcpy(TMPtab[bla][bla].zustand,a.Tab,15);

C++:
TMPtab[bla][bla].zustand[0] = 0;
TMPtab[bla][bla].zustand[1] = 1;
TMPtab[bla][bla].zustand[2] = 2;
TMPtab[bla][bla].zustand[3] = -16777213; // Fehler?
TMPtab[bla][bla].zustand[4] = -1;
TMPtab[bla][bla].zustand[5] = -1;
TMPtab[bla][bla].zustand[6] = -1;
TMPtab[bla][bla].zustand[7] = -1;
TMPtab[bla][bla].zustand[8] = -1;
TMPtab[bla][bla].zustand[9] = -1;
TMPtab[bla][bla].zustand[10] = -1;
TMPtab[bla][bla].zustand[11] = -1;
TMPtab[bla][bla].zustand[12] = -1;
TMPtab[bla][bla].zustand[13] = -1;
TMPtab[bla][bla].zustand[14] = -1;





lg
rejo
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
29.03.2005, 11:09 Uhr
Tommix



Hallo,
Du kopierst 15 Bytes, meinst aber eher

C++:
memcpy(TMPtab[bla][bla].zustand,a.Tab, 15*sizeof(int));

oder so.
Allerdings würde ich mich generell eher an Beefys Ansatz orientieren.

- Tommix
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
29.03.2005, 11:38 Uhr
rejo



Danke Tommix!
Ich kenn mich noch nicht so gut aus das ich den Ansatz von Beefy ganz versteh.
Aber trotzdem danke für den Tipp!

lg
rejo
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: