Automaten (Akzeptoren)

[Nasenbaer]

Ich hab mal ne Frage zu den Akzeptoren. Kann so ein Automat eine leere Menge an Endzuständen besitzen und darf auch die Übergangsfunktion nur die leere Menge als Wertebereich haben?

Es geht mir dabei darum ob ein Automat mit nur einem Zustand auch die leere Menge als Sprache akzeptiert oder ob diese per Definition keine Sprache ist.

[Sephiroth]

Lass und mal überlegen ...
Die Menge der Zustände S darf nicht leer sein (per Definition), die Übergangsfunktion bildet von S x Σ -> S ab, folglich muß wieder ein Zustand dabei herauskommen.
Aber, die Menge der Endzustände E ist lediglich eine Teilmenge von S, kann also auch die leere Menge sein, da die bekanntlich Teilmenge einer jeden Menge ist.

Ein Automat der die leere Menge akzeptiert ist möglich, indem er immer im Startzustand bleibt. Dann ist E = Ø und die akzeptierte Sprache ist die leere Sprache (eine leere Menge). Die leere Menge ist übrigens ein regulärer Ausdruck und wir wissen, daß die äquivalent zu Typ-3 Grammatiken (reg. Grammatiken) sind, welche eine reguläre Sprache erzeugen.

p.s.
Außerdem, eine formale Sprache ist eine Teilmenge der Menge aller Wörter über einem nichtleeren Alphabet, also kann es auch wieder die leere Menge sein.

[AlSvartr]

Zustimmung von meiner Seite :)

Allerdings würde ich doch sagen, dass eigentlich jeder Automat die leere Sprache akzeptiert. Ausnahme: Man könnte sich streiten, was ist, wenn der Startzustand auch Endzustand ist..denn dann akzeptiert der Automat automatisch an dieser Stelle das leere Wort ;)

[Nasenbaer]

Ok gut zu wissen. :)

Und noch ne kleine Frage ist X* regulär, wenn X beliebig. Ich meine nein aber ein Kumpel beharrt auf ja. Er meint man könne jedes beliebige Wort aus X* durch eine reguläre Grammatik erzeugbar ist.

[Sephiroth]

Äh, nein, wie will er z.B. die Sprache L = {anbn | n>0} (und X = {a,b}) mit einem regulären Ausdruck bzw. regulären Grammatik erzeugen? Nach seiner Behauptung müsste er die Wörter alle erzeugen können.

Außerdem würde man ja dann mit regulären Grammatiken alles beschreiben können, was eben nicht geht. ^^

[Sephiroth]

Allerdings würde ich doch sagen, dass eigentlich jeder Automat die leere Sprache akzeptiert. Ausnahme: Man könnte sich streiten, was ist, wenn der Startzustand auch Endzustand ist..denn dann akzeptiert der Automat automatisch an dieser Stelle das leere Wort ;)
Dieser Automat akzeptiert alles, somit ist die Menge nicht leer. Selbst die Menge mit dem leeren Wort als einziges Element ist nicht leer.

[AlSvartr]

Hm hm..das leuchtet mir ja einerseits ein, aber ist es nicht andererseits so, dass wenn ein Automat die Sprache L akzeptiert, er auch gleichzeitig alle Sprachen Li element P(L) akzeptiert?

[Nasenbaer]

Äh, nein, wie will er z.B. die Sprache L = {anbn | n>0} (und X = {a,b}) mit einem regulären Ausdruck bzw. regulären Grammatik erzeugen? Nach seiner Behauptung müsste er die Wörter alle erzeugen können.

Außerdem würde man ja dann mit regulären Grammatiken alles beschreiben können, was eben nicht geht. ^^

Er sagt so: (S sei das Startsymbol)
S -> € (leeres Wort)
S -> aS
S -> bS

Damit könnte man zwar mehr erzeugen als die obige Sprache aber das darf sie ja, weil X* akzeptiert werden soll und nicht nur ein bestimmter Teil davon wie L z.B.

[AlSvartr]

Damit kann man aber doch nicht nur mehr erzeugen, sondern quasi alles, und das ist nicht nur X*, es sei denn, X={a,b}...

[Nasenbaer]

Was denn noch?

[AlSvartr]

Na du erzeugst alle Wörter in (a|b)*...aber wenn X beliebig ist, dann kann X eben auch NICHT regulär sein (wie oben die Sprache anbn). Für die Beispielsprache ist dann X* doch genau {(anibni)j|ni element N0, j element N0}, und das ist nicht regulär.

Für reguläres X gilt allerdings durchaus, dass X* regulär ist.

[Sephiroth]

hm ... ich schätze ich hab mich zu sehr auf die echte Teilmenge konzentriert. ;(

Wenn L = X*, dann wäre das doch eigentlich trivialerweise erfüllt. Ein Automat, dessen Start- und Endzustand der selbe ist. Der Akzeptiert alles aus X* und somit genau X*. Die Regeln einer Grammatik wären dann S -> x1|..|xn|x1S|..|xnS|€
Reguläre Ausdruck: (x1 u .. u xn)*

[Nasenbaer]

Hmm versteh ich nicht aber er hat sich das folgendermaßen gedacht:

Ich hab ein Alphabet X, das per Def. endlich sein muss. Darum erstelle eine Grammatik mit folgenden Regeln:
S -> €
und für jedes Element aus X eine Regel der Form
S -> xS (wobei x ein beliebiges Element aus X ist)

Somit erzeugt man X*. Und auch genau X*. Will man nur Teilmengen davon erzeugen so klappt das nicht.

Darum meint er diese Aussage wäre richtig:
Sei X ein Alphabet, dann ist die Sprache X* regulär.

Ich meine das Gegenteil aber finde keinen Fehler in seiner Behauptung.

[Nasenbaer]

hm ... ich schätze ich hab mich zu sehr auf die echte Teilmenge konzentriert. ;(

Wenn L = X*, dann wäre das doch eigentlich trivialerweise erfüllt. Ein Automat, dessen Start- und Endzustand der selbe ist. Der Akzeptiert alles aus X* und somit genau X*. Die Regeln einer Grammatik wären dann S -> x1|..|xn|x1S|..|xnS|€
Ok du meinst das also auch. Hmm
x1|..|xn sind übrigens überflüssig da aus xnS durch S -> € das Ergebnis xn ist.

[Sephiroth]

Na du erzeugst alle Wörter in (a|b)*...aber wenn X beliebig ist, dann kann X eben auch NICHT regulär sein (wie oben die Sprache anbn). Für die Beispielsprache ist dann X* doch genau {(anibni)j|ni element N0, j element N0}, und das ist nicht regulär.

Für reguläres X gilt allerdings durchaus, dass X* regulär ist.
Also X ist stets regulär, da es endlich sein soll. Wenn es das nicht ist, brauchen wir gar nicht weiter reden. ^^
Ich glaube ich weiß was du ausdrücken willst, du willst die von mir genannte Sprache L als Alphabet verwenden. Das geht aber nicht, da die Sprache/Menge nicht endlich ist.

Halten wir fest, X beliebig aber endlich, dann ist X* regulär, sonst gilt die Aussage nicht.

[AlSvartr]

Ok..ich würde mal sagen, der Knackpunkt ist hier doch, dass X ein Alphabet ist und nicht etwa eine Sprache...letzteres war meine Betrachtungsweise..war ja auch nicht wirklich anders angegeben, oder? :D

[Sephiroth]

Naja, es ist es egal, wenn die Sprache auch endlich (und somit regulär) ist. Dann sind eben die Elemente des Alphabets Wörter und keine Buchstaben. :D

p.s.
verdammt, ich wollte heute doch noch vor Minority Report nen Film gucken aber nö ....

[AlSvartr]

Dass es für reguläre Sprachen gilt, hatte ich ja schon geschrieben.. ;) ... aber eine reguläre Sprache kann ja auch unendlich sein (wie z.B. {an|n element N})...und auch dann ist das alles in Ordnung ;)

Film gucken..Minority Report..hm..Film gucken, Film gucken..mir ist langweilig..hat jemand Ahnung von Mock-Objekten? (mal n bisschen Offtopic, aber noch im richtigen Forenbereich :D)