Endlicher Automat

R

rejo

0
Hallo Leute ;)

Könnt ihr mir vielleicht paar Ideen geben wie ne Datenstruktur für einen Endlichen Automaten aussehen soll?
Das Programm soll von einem Nichtdeterministischen Automaten in ein Deterministischen Automaten umwandeln... und dann muss es eine Methode geben womit mein den Syntax checken soll.

Habt ihr irgendwelche Ideen?

lg
rejo
 
aaaaahhhh wie komplex und durcheinander...

du willst ne art parser bzw copiler bauen hab ich das soweit richtig?

red mal deutsch ;)
 
@ink3n: Er redet deutsch. Nur weil du es nicht verstehst, ist das nicht automatisch quatsch, was er schreibt.

So, schön hier mal nen thread aus der theoretischen Informatik zu haben.
Ich würde dir raten, dich strickt an die mathematische definition von Automaten zu halten. Ich nehme an wir reden von Automaten, die eine Eingabe einmal durchgehen und dann entsprechende Zustandsänderungen durchführen.
Also: Nimm deine Zustände und numeriere sie. Dann speicher sie in einem Array.
Jetzt codiere die Überführungsfunktion durch einen Zustand, ein Eingabe Zeichen und noch einen Zustand.
Wenn du das hast, ist die Umwandlung von NDEA zu DEA ziemlich leicht.
 
hab ich das gesagt? X(

echt, ich habe gesagt das er es mal so schreiben könnte das ich es auch verstehe und nicht da es quatsch ist du held mit deinen 2 sternchen..., solln das?

Scheint hier ne art zu sein zu zeigen das man mehr wissen hat , ich mein das man andere gleich erstal anfährt und das wort im mund umdreht.... vielen dank auch
 
[OT]
@ink3n was würde es bringen wenn rejo sein post so verfasst das auch du ihn verstehst ? du könntest ihm dann doch trozdem nich helfen :/
Das ist so schrecklich, dass heute jeder Idiot zu allem eine Meinung hat. Ich glaube, das ist damals falsch verstanden worden mit der Demokratie: Man darf in der Demokratie eine Meinung haben, man muss nicht. Es wäre ganz wichtig, dass sich das mal rumspricht. Wenn man keine Ahnung hat, einfach mal Fresse halten.
Quelle
Zum Vergrößern anklicken....
[/OT]

mfg

püppi
 
wie ich schon sagte...die art und weise ist echt zum kot***

@puppe evnt. kann man nicht helfen aber lernen? was ist wenn ich mal vor der selben problematik stehe, soll ich noch nen threat anfangen? betrachte das mal von der seite...
 
@ink3n wenn du mal vor der gleichen Problematik stehst, weist du ach was für automaten es gibt und verstehst den post wunderbar.
das du was lernen willst is ja auch in ordnung, aber ist es rejos aufgabe dir was bei zu bringen ? du kannst doch auch einfach bei wiki oder google nach lesen, so schwer sind automaten nich zu verstehen.

faule menschen finde ich echt zum kot***

mfg

püppi
 
wenn rejo eine frage zum thema nichtdeterministische endliche automaten hat, kann er sie ja wohl einfach stellen. wenn ich eine frage zum thema c++ habe, werde ich auch nicht erst eine fette erklärung verfassen.

und bezüglich umgangsstil:
fass dich doch bitte erstmal an deine nase, lies dir den thread durch, den du verfasst hast und dann erklär mir seinen sinn. wenn du eine frage zu dem thema gestellt hättest, hätte ich sie dir ja auch gerne beantwortet. aber so einen sinnlosen beitrag zu schreiben und sich dann noch über eine antwort beschweren, das ist ziemlich arm.
 
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 :)

Code: 
#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

Code: 
#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*sizeof(int));
		}
	}

	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";
	}
}

Code: 
#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
 
Ich würde das ganze nicht unbedingt so verkomplizieren.
Das geht bestimmt deutlich einfacher.

Ich habe leider im Moment gerade nicht viel Zeit, aber ich versuch mal, dir nen ansatz noch heute zu schreiben.
 
So, Sorry, dass es so lange gedauert hat, aber ich habe zur Zeit viel um die Ohren.

Muss das denn unbedingt C++ sein? Da ist es nämlich schwer einen verständlichen Code zu schreiben, aber ich will dir mal das Grundprinzip erläutern:

1. Du hast eine endliche Menge von Zuständen. Jeder dieser Zustände hat einen eindeutigen Namen, einen bool Wert, der angibt, ob der Zustand akzeptierend ist und variabel viele Zustände mit jeweils dem dazugehörenden Zeichen, in die er überführt.

2. Es bietet sich an, diese Zustände baumartig miteinander zu verketten, die Wurzel des Baumes stellt deinen Startzustand dar.

3. Jetzt brauchst du eine Funktion, die rekursiv auf dem Baum überprüft, ob das erste Zeichen des eingegebenen Wortes zu irgendeinem nachgeordneten Zustand passt. Für jeden Zustand, der passt, ruft sich die Funktion wieder selber auf, die Rückgabewerte werden mit false OR-verknüpft. Passt kein Zeichen, wird false zurückgegeben, ist das Wort leer, wird der bool-Wert des aktuellen Zustandes zurückgegeben.

Wenn du das soweit hast, melde dich, dann kommen wir zum schwierigen Teil.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben