# kennt sich jemand mit endlichen automaten aus?



## Heyoka955 (8. Apr 2019)

wir haben im fach cl ein blatt aufbekommen und ich habe das in der Vorlesung nul verstanden, und ich brauche hilfe bei Automaten vorallem.

also aufgabe 1


----------



## thecain (8. Apr 2019)

Wie wärs mit Eigeninitiative und mal selber Google bemühen. Da gibt's massenhaft Lektüre zu.


----------



## Xyz1 (8. Apr 2019)

Hier mal Aufgabe 1 (1. 2. 3.), ohne nicht akzeptierenden Zustand:



Bei Fehlern einfach laut "Hier!" rufen.


----------



## Xyz1 (8. Apr 2019)

Ups, ich habe einen b-Kringel bei 1 2. q1 vergessen! (keine Absicht!)


----------



## httpdigest (8. Apr 2019)

Tobias-nrw hat gesagt.:


> Bei Fehlern einfach laut "Hier!" rufen.


Hier! 

Ich würde argumentieren, dass dein erster Automat für "w enthält genau ein a" falsch ist. Er landet auch für das Wort w="aaa" im akzeptierenden Endzustand q1. Du hast zwar geschrieben "ohne nicht akzeptierenden Zustand", aber den braucht man definitiv, bzw brauchst du einfach mehr Zustände, um von q1 mit einem weiteren 'a' wieder wegzukommen zu einem Zustand, den man nicht mehr verlassen kann.

Dein zweiter Automat ist auch falsch, da hier nicht gelten muss, dass "jedes 'a' in w folgt unmittelbar auf ein 'b'". Dein Automat akzeptiert ja auch w="baaaa" (in diesem Wort folgt eben nicht jedes 'a' unmittelbar auf ein 'b').

Der dritte Automat ist ebenfalls falsch, da er w="b" sowie w="bb" und auch w="ababa" nicht erkennt.


----------



## Heyoka955 (8. Apr 2019)

httpdigest hat gesagt.:


> Hier!
> 
> Ich würde argumentieren, dass dein erster Automat für "w enthält genau ein a" falsch ist. Er landet auch für das Wort w="aaa" im akzeptierenden Endzustand q1. Du hast zwar geschrieben "ohne nicht akzeptierenden Zustand", aber den braucht man definitiv, bzw brauchst du einfach mehr Zustände, um von q1 mit einem weiteren 'a' wieder wegzukommen zu einem Zustand, den man nicht mehr verlassen kann.
> 
> ...


ich hane echt keine Ahnung von dem Thema, hoffe dass der prof das morgen erklärt in theoretische Informatik ansonsten bye !!!
ich habe chiermosky Hierarchie alles verstanden.


----------



## httpdigest (8. Apr 2019)

Heyoka955 hat gesagt.:


> ich habe chiermosky Hierarchie alles verstanden.


chiermosky Hierarchie.... genau.
*Chomsky*!!!!


----------



## Heyoka955 (8. Apr 2019)

httpdigest hat gesagt.:


> chiermosky Hierarchie.... genau.
> *Chomsky*!!!!


hauptsache ich weiß wie es geht lol haha


----------



## httpdigest (8. Apr 2019)

lol... haha...


----------



## Heyoka955 (8. Apr 2019)

httpdigest hat gesagt.:


> lol... haha...


kannst du mir vllt erklären was die aufgabe verlangt?



The depth of an integer n is defined to be how many multiples of n it is necessary to compute before all 10 digits have appeared at least once in some multiple.


example:

let see n=42

Multiple         value         digits     comment
42*1              42            2,4 
42*2              84             8         4 existed
42*3              126           1,6        2 existed
42*4              168            -         all existed
42*5              210            0         2,1 existed
42*6              252            5         2 existed
42*7              294            9         2,4 existed
42*8              336            3         6 existed 
42*9              378            7         3,8 existed

Looking at the above table under digits column you can find all the digits from 0 to 9, Hence it required 9 multiples of 42 to get all the digits. So the depth of 42 is 9. Write a function named computeDepth which computes the depth of its integer argument.Only positive numbers greater than zero will be passed as an input.


----------



## httpdigest (8. Apr 2019)

Diese Codewars Aufgabe hat doch mit diesem Thema überhaupt nichts mehr zu tun...


----------



## Heyoka955 (8. Apr 2019)

httpdigest hat gesagt.:


> Diese Codewars Aufgabe hat doch mit diesem Thema überhaupt nichts mehr zu tun...


dann frage ich privat


----------



## httpdigest (8. Apr 2019)

Nein. Du machst einen neuen Thread mit dieser Frage auf.... alter Schwede.


----------



## mrBrown (8. Apr 2019)

Heyoka955 hat gesagt.:


> dann frage ich privat


Mach einfach ein neues Thema auf...


----------



## Xyz1 (8. Apr 2019)

httpdigest hat gesagt.:


> "w enthält genau ein a"


Scheiße, ich habe das "genau ein" überlesen... Dann muss bei "a, b" das "a, " gestrichen werden.



httpdigest hat gesagt.:


> Dein zweiter Automat ist auch falsch,


Das musst du genau lesen  "b über a" bedeutet hier, a v.l.n.r. und b v.r.n.l. ... Das heißt, ein zusätzliches a in q2 wäre unzulässig/ nicht akzeptierend - und damit wärs richtig.



httpdigest hat gesagt.:


> Der dritte Automat ist ebenfalls falsch,


Ja das stimmt... Obwohl ich mir viel Mühe bei gegeben habe, müssen da überall noch b-Kringel dran...

Gut das man nochmal darüber diskutiert... Aber auch DEAs mit impliziten, nicht akzeptierenden Endzuständen können formal korrekt sein... wenn man schreibfaul ist. 

@Heyoka955 Die anderen/ übrigen Aufgaben leiten sich eigentlich daraus ab, wenn man erstmal den Anfang hat...


----------



## Heyoka955 (8. Apr 2019)

Tobias-nrw hat gesagt.:


> Scheiße, ich habe das "genau ein" überlesen... Dann muss bei "a, b" das "a, " gestrichen werden.
> 
> 
> Das musst du genau lesen  "b über a" bedeutet hier, a v.l.n.r. und b v.r.n.l. ... Das heißt, ein zusätzliches a in q2 wäre unzulässig/ nicht akzeptierend - und damit wärs richtig.
> ...


ich setzet mich mit kollegen da ran und machen die dann.


----------



## Xyz1 (8. Apr 2019)

Heyoka955 hat gesagt.:


> ich setzet mich mit kollegen da ran und machen die dann.


Roger.


----------



## mihe7 (8. Apr 2019)

Die Bedingung, dass ein Wort w genau ein "a" enthält bedeutet ja nichts anderes, als dass
1. das Wort mit beliebig vielen (auch 0) "b" beginnen darf,
2. auf den (ggf. leeren) Wortanfang ein "a" folgen muss und
3. anschließend beliebig viele weitere "b" folgen dürfen

ad 1.: das lässt sich mit einem Startzustand, nennen wir ihn mal q0, realisieren, der durch ein "b" auf sich selbst überführt wird. Diesen Zustand kann man sich als "habe bisher noch kein 'a' gesehen"-Zustand vorstellen. Dieser Zustand darf nicht zugleich Endzustand sein, da noch kein "a" im Wort vorhanden ist.

ad 2.: wurde im Startzustand kein "b" sondern ein "a" gelesen, geht der Automat in einen neuen Zustand, nennen wir ihn mal q1, über. Das ist der Zustand "habe bereits ein 'a' gesehen". Das muss ein Endzustand sein, denn die Voraussetzung, dass das Wort ein a enthält, ist dort erfüllt. 

ad 3.: hat man bereits ein "a" gelesen (Automat ist im Zustand q1), können beliebig viele weitere "b" folgen. Das erreicht man wie unter 1, indem man den Zustand auf sich selbst überführt.

Für einen Automaten A=(Q, s, S, F, d) mit der Zustandsmenge Q:={q0, q1}, dem Startzustand s:={q0}, dem Eingabealphabet S:={a,b}, dem Endzustand F:={q1} kann dann die Übergangsfunktion d: Q x S -> Q wie folgt angegeben werden: d:={(q0, b, q0), (q0, a, q1), (q1, b, q1)}

Den Rest kannst Du selber machen.


----------



## Xyz1 (8. Apr 2019)

Danke @mihe7 für diese "vollumfängliche" Erklärung von Dir. Zusammen mit der "bildlichen" Darstellung hätte er damit für Aufgabe 1 1. die volle Punktzahl, denke ich (wo will man noch etwas hinzufügen? usw).

Die andere Sache ist die... dass er in der Vorlesung (angeblich) gar nichts versteht... ? Warum nicht? Woran liegt das? Was müsste sich ändern? usw usf.


----------



## mihe7 (8. Apr 2019)

Tobias-nrw hat gesagt.:


> Die andere Sache ist die... dass er in der Vorlesung (angeblich) gar nichts versteht... ? Warum nicht? Woran liegt das? Was müsste sich ändern? usw usf.


Ja, darum habe ich das mal sehr ausführlich gemacht und auch nur für die erste (= einfachste) der Aufgaben  Warum er in der Vorlesung nichts verstanden hat, weiß ich nicht. Die Funktionsweise von Automaten ist ja nun wirklich nicht so schwer zu verstehen. Ich hoffe halt für ihn, dass er aus der Erklärung was mitnehmen kann, bekomme aber Zweifel, wenn ich lese "und machen die dann."


----------



## Xyz1 (8. Apr 2019)

So kommen wir nicht weiter.  "und mache die dann" kann auch einfach nur so dahingeschrieben sein... Ich lege mich jetzt schlafen, habe schon die Befürchtung, dass noch um 3 Uhr wieder Beiträge geschrieben werden heute/morgen... Bis dann.


----------



## mihe7 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> dass noch um 3 Uhr wieder Beiträge geschrieben werden heute/morgen...


Das liegt im Bereich des Möglichen. Gute Nacht.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Ja, darum habe ich das mal sehr ausführlich gemacht und auch nur für die erste (= einfachste) der Aufgaben  Warum er in der Vorlesung nichts verstanden hat, weiß ich nicht. Die Funktionsweise von Automaten ist ja nun wirklich nicht so schwer zu verstehen. Ich hoffe halt für ihn, dass er aus der Erklärung was mitnehmen kann, bekomme aber Zweifel, wenn ich lese "und machen die dann."


so ? zu 1 und 2


----------



## Heyoka955 (9. Apr 2019)

Heyoka955 hat gesagt.:


> so ? zu 1 und 2


----------



## mihe7 (9. Apr 2019)

Nein. Bei Aufgabe 1 fehlt mind. eine Kante, bei Aufgabe 2 hast Du Kanten ohne Beschriftung und bei Aufgabe 3 keinen Endzustand.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Nein. Bei Aufgabe 1 fehlt mind. eine Kante, bei Aufgabe 2 hast Du Kanten ohne Beschriftung und bei Aufgabe 3 keinen Endzustand.


besser kriege ich es nicht hin.


----------



## Xyz1 (9. Apr 2019)

@httpdigest So falsch war meins gar nicht... sogar verdammt nah an richtig...

null bedeutet nicht akzeptierender Endzustand, true akzeptiert, false nicht akzeptiert und (f) steht an Endzuständen dran:

```
List<Uebergang> a = List.of(
            new Uebergang("q0", "b", "q0", false),
            new Uebergang("q0", "a", "q1", true),
            new Uebergang("q1", "b", "q1", true));
    test(a);

    List<Uebergang> b = List.of(
            new Uebergang("q0", "b", "q1", true),
            new Uebergang("q1", "b", "q1", true),
            new Uebergang("q1", "a", "q2", true),
            new Uebergang("q2", "b", "q1", true));
    test(b);

    List<Uebergang> c = List.of(
            new Uebergang("q0", "b", "q0", true),
            new Uebergang("q0", "a", "q1", false),
            new Uebergang("q1", "b", "q1", false),
            new Uebergang("q1", "a", "q2", false),
            new Uebergang("q2", "b", "q2", false),
            new Uebergang("q2", "a", "q3", true),
            new Uebergang("q3", "b", "q0", true),
            new Uebergang("q3", "a", "q1", false));
    test(c);
```


```
Testing [(q0,b,q0), (q0,a,q1(f)), (q1,b,q1(f))]:
aaaa => null
aaab => null
aaba => null
aabb => null
abaa => null
abab => null
abba => null
abbb => true
baaa => null
baab => null
baba => null
babb => true
bbaa => null
bbab => true
bbba => true
bbbb => false
Testing [(q0,b,q1(f)), (q1,b,q1(f)), (q1,a,q2(f)), (q2,b,q1(f))]:
aaaa => null
aaab => null
aaba => null
aabb => null
abaa => null
abab => null
abba => null
abbb => null
baaa => null
baab => null
baba => true
babb => true
bbaa => null
bbab => true
bbba => true
bbbb => true
Testing [(q0,b,q0(f)), (q0,a,q1), (q1,b,q1), (q1,a,q2), (q2,b,q2), (q2,a,q3(f)), (q3,b,q0(f)), (q3,a,q1)]:
aaaa => false
aaab => true
aaba => true
aabb => false
abaa => true
abab => false
abba => false
abbb => false
baaa => true
baab => false
baba => false
babb => false
bbaa => false
bbab => false
bbba => false
bbbb => true
```

Damit ist Aufgabe 1 jetzt gelöst.


----------



## Heyoka955 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> @httpdigest So falsch war meins gar nicht... sogar verdammt nah an richtig...
> 
> null bedeutet nicht akzeptierender Endzustand, true akzeptiert, false nicht akzeptiert und (f) steht an Endzuständen dran:
> 
> ...


hab ich das richtig oder wie ?


----------



## Xyz1 (9. Apr 2019)

Heyoka955 hat gesagt.:


> hab ich das richtig oder wie ?


nein, ich meinte damit einfach meinen Beitrag #3 ..


----------



## Heyoka955 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> nein, ich meinte damit einfach meinen Beitrag #3 ..


dann weiß ich nicht mehr weiter...


----------



## mihe7 (9. Apr 2019)

@Heyoka955 sag mal, das kannst Du doch jetzt nicht ernst meinen. Der Graph ist in Kommentar #18 komplett definiert und Du schaffst es nicht, ein Bild dazu zu malen. Das kann doch nicht so schwer sein, eine Übergangsfunktion, die gerade mal drei Kanten eines Graphen angibt, korrekt auf ein Bild zu übertragen.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> @Heyoka955 sag mal, das kannst Du doch jetzt nicht ernst meinen. Der Graph ist in Kommentar #18 komplett definiert und Du schaffst es nicht, ein Bild dazu zu malen. Das kann doch nicht so schwer sein, eine Übergangsfunktion, die gerade mal drei Kanten eines Graphen angibt, korrekt auf ein Bild zu übertragen.


Ich habe mir den Code nicht genau angeschaut weil ich auf eine antowrt wollte uns Feedback dazu.


----------



## mihe7 (9. Apr 2019)

Kommentar #18 hat keinen Code.


----------



## Xyz1 (9. Apr 2019)

@Heyoka955 Ich verstehe ja dass das für Dich alles neu ist usw., allerdings steht die Lösung quasi schon in Kommentar #3 und in Kommentar #27 ... Das heißt, diese könntest Du einfach nehmen.
Und ja ich kenne auch Vorlesungen bei denen man einfach nichts verstehen kann. Dann musst Du Dir dieses Wissen irgendwie anders zulegen. Wie läuft es denn mit den anderen und mit denen Du lernen und Zettel lösen wolltest? ... (Aber Lektüre kaufen ist erst einmal nur gut für den Geldbeutel des jeweiligen Autor.  ) 
Wahrscheinlich kommen jetzt 1.000 Gegenfragen, deswegen sach ich schon einmal dass ich morgen erst wieder ins Forum schauen kann. Bis dann!


----------



## MoxxiManagarm (9. Apr 2019)

Tobias-nrw hat gesagt.:


> List<Uebergang> c = List.of( new Uebergang("q0", "b", "q0", true), new Uebergang("q0", "a", "q1", false), new Uebergang("q1", "b", "q1", false), new Uebergang("q1", "a", "q2", false), new Uebergang("q2", "b", "q2", false), new Uebergang("q2", "a", "q3", true), new Uebergang("q3", "b", "q0", true), new Uebergang("q3", "a", "q1", false)); test(c);


Ich verstehe noch nicht wie du auf 4 Zustände kommst. Die Aufgabe heißt doch "die Anzahl a’s in w ist ein Vielfaches von 3". Demnach gibt es die Zustände "|a| % 3 = 0" (q0), "|a| % 3 = 1" (q1) und "|a| % 3 = 2" (q2), wobei alleine q0 akzeptierend ist.

Also:

```
----> q0* --a--> q1 --a--> q2
      ^----------a----------`
```

(habe b in dem Graphen herausgelassen, bitte zu jedem Zustand eine selbstreferenzierende Kante denken)


----------



## Heyoka955 (9. Apr 2019)

I


Tobias-nrw hat gesagt.:


> @Heyoka955 Ich verstehe ja dass das für Dich alles neu ist usw., allerdings steht die Lösung quasi schon in Kommentar #3 und in Kommentar #27 ... Das heißt, diese könntest Du einfach nehmen.
> Und ja ich kenne auch Vorlesungen bei denen man einfach nichts verstehen kann. Dann musst Du Dir dieses Wissen irgendwie anders zulegen. Wie läuft es denn mit den anderen und mit denen Du lernen und Zettel lösen wolltest? ... (Aber Lektüre kaufen ist erst einmal nur gut für den Geldbeutel des jeweiligen Autor.  )
> Wahrscheinlich kommen jetzt 1.000 Gegenfragen, deswegen sach ich schon einmal dass ich morgen erst wieder ins Forum schauen kann. Bis dann!


ich bin nicht zur Uni gegangen, wollte die Aufgabe selbst lösen. 
Habe Videos angeschaut und intuitiv gearbeitet.


----------



## MoxxiManagarm (9. Apr 2019)

Heyoka955 hat gesagt.:


> ich bin nicht zur Uni gegangen, wollte die Aufgabe selbst lösen.
> Habe Videos angeschaut und intuitiv gearbeitet.


Dann lass dir was raten, von jemanden der auch nie auf der Uni war und sich alles quasi selbst beigebracht hat:
Überlege dir Bezeichnungen für die Zustände, Beispiel bezogen auf Aufgabe 1:

*w enthält genau ein a*
q0: enthält (noch) kein a
q1: enthält genau ein a

*jedes a in w folgt unmittelbar auf ein b *
q0: hatte kein vorhergehendes Event
q1: letztes Event war ein b
q2: letztes Event war ein a

*die Anzahl a’s in w ist ein Vielfaches von 3*
q0: Anzahl a % 3 = 0
q1: Anzahl a % 3 = 1
q2: Anzahl a % 3 = 2

Mit diesen Bezeichnungen fällt es einfacher dir logisch zu überlegen welche Events von welchem Zustand aus überhaupt existieren (gültig sind) und zu welchem Zustand sie führen.


----------



## Xyz1 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Ich verstehe noch nicht wie du auf 4 Zustände kommst


Stimmt, der "Graph" zu A 1 3. ist bei mir nicht minimal, sondern hat einen Zustand mehr.


```
List<Uebergang> c = List.of(
            new Uebergang("q0", "b", "q0", true),
            new Uebergang("q0", "a", "q1", false),
            new Uebergang("q1", "b", "q1", false),
            new Uebergang("q1", "a", "q2", false),
            new Uebergang("q2", "b", "q2", false),
            new Uebergang("q2", "a", "q0", true));
    test(c);
```

Ergebnis: same


----------



## MoxxiManagarm (9. Apr 2019)

Die kantenbasierte Implementierung von @Tobias-nrw ist eine Möglichkeit. Ich selbst finde die Event-basierte Variante anschaulicher. Daher hier auch einmal ein Beispiel für Aufgabe 1.1:


```
public class StateMachine {
    public enum State1 {
        Q0(false), // no 'a' event happened
        Q1(true); // exact 1 'a' event happened
        
        private boolean accepting;
        
        private State1(boolean accepting) {
            this.accepting = accepting;
        }
        
        public boolean isAccepting() {
            return accepting;
        }
        
        public State1 onA() {
            switch(this) {
                case Q0: return Q1;
            }
            
            return null;
        }
        
        public State1 onB() {
            switch(this) {
                case Q0: return Q0;
                case Q1: return Q1;
            }
            
            return null;
        }
    }
    
    public static boolean test(String events) {
        State1 state = State1.Q0; // initial
        
        for(int i = 0; i < events.length(); i++) {
            switch(events.charAt(i)) {
                case 'a': state = state.onA(); break;
                case 'b': state = state.onB(); break;
                default: return false; // unhandled event occured
            }
            
            if(state == null) return false;
        }
        
        return state.isAccepting();
    }
    
    public static void main(String args[]) {
        System.out.println(test("")); // false
        System.out.println(test("a")); // true
        System.out.println(test("b")); // false
        System.out.println(test("bb")); // false
        System.out.println(test("bab")); // true
        System.out.println(test("ba")); // true
        System.out.println(test("aa")); // false
    }
}
```


----------



## Xyz1 (9. Apr 2019)

@MoxxiManagarm Wie ich es implementiert habe ist doch meine Sache...

Aber ich möchte Dir trotzdem einen kleinen Tipp geben 

```
for (int i = 0; i < 16; i++) {
    String w = String.format("%04d", Integer.parseInt(Integer.toBinaryString(i))).replace('0', 'a').replace('1', 'b');

}
```

Bis dann.


----------



## MoxxiManagarm (9. Apr 2019)

Tobias-nrw hat gesagt.:


> @MoxxiManagarm Wie ich es implementiert habe ist doch meine Sache...


Habe doch nichts anderes gesagt. Ich wollte die andere Variante nur ergänzen weil ich sie selbst anschaulicher finde und hoffe es hilft ihm endlich den Schalter umzulegen.



> Aber ich möchte Dir trotzdem einen kleinen Tipp geben


Wenn man so viele Testfälle haben will dann klar.


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Habe doch nichts anderes gesagt. Ich wollte die andere Variante nur ergänzen weil ich sie selbst anschaulicher finde und hoffe es hilft ihm endlich den Schalter umzulegen.
> 
> 
> Wenn man so viele Testfälle haben will dann klar.


----------



## mihe7 (9. Apr 2019)

1a) passt
1b) habe ich mir inhaltlich nicht angesehen, da kein Endzustand vorhanden.
1c) wo ist das b?


----------



## MoxxiManagarm (9. Apr 2019)

mihe7 hat gesagt.:


> 1b) habe ich mir inhaltlich nicht angesehen, da kein Endzustand vorhanden.


Kann auch nicht passen, müssten schließlich 3 Zustände sein.



mihe7 hat gesagt.:


> 1c) wo ist das b?


Er hat nur meinen Ascii-Graphen abgezeichnet und meinen Kommentar darunter nicht gesehen ;-)


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> 1a) passt
> 1b) habe ich mir inhaltlich nicht angesehen, da kein Endzustand vorhanden.
> 1c) wo ist das b?


Weißt du wie die b geht ?


----------



## MoxxiManagarm (9. Apr 2019)

Heyoka955 hat gesagt.:


> Weißt du wie die b geht ?


Das haben wir doch bereits deutlich gemacht. Du hast 3 Zustände.
q0: Noch kein Event a oder b stattgefunden
q1: Event b zuvor stattgefunden
q2: Event a zuvor stattgefunden

Stell dir zu jedem Zustand die Frage, darf Event a bzw. b stattfinden? Wenn ja, welcher Zustand folgt daraus?

Beispiel:
Du bist am Anfang der Eventkette (Initial State = q0).
Q: Darf dann Event a stattfinden mit der Aufgabenstellung, dass Event b unmittelbar vor Event a eingetreten sein muss
A: Nein darf es nicht --> du hast keine ausgehende Kante von q0 mit der Bezeichnung a.
Q: Darf dann Event b stattfinden?
A: Ja, der Folgezustand ist folgerichtig "Event b hat stattgefunden", also q1 --> du hast eine Kante b von q0 nach q1

Das sind in der Zahl 3x2=6 Fragestellungen, beantworte Sie für dich und mal sie auf.


----------



## MoxxiManagarm (9. Apr 2019)

Vielleicht hilft dir ja auch eine Verbildlichung. Nehmen wir eine Küche.

Initial State q0 = Du bist in der Küche mit einem leeren Küchentisch
Event b = du kochst etwas, q1 = es steht Essen auf dem Tisch
Event a = du isst alles was auf dem Tisch steht, q2 = die Teller auf dem Tisch sind nun leer

Logischer Weise kannst du nur was warmes Essen, wenn du zuvor etwas gekocht hast. b muss also stattgefunden haben.
q0: Kannst du etwas essen, wenn du gerade erst in die Küche gekommen bist?
q0: Kannst du etwas kochen, wenn du gerade erst in die Küche gekommen bist?
q1: Du hast gerade gekocht, kannst du nun essen?
q1: Du hast gerade gekocht, kannst du noch mehr kochen?
q2: Du hast gerade alles aufgegessen. Kannst du noch mehr essen?
q2: Du hast gerade alles aufgegessen. Kannst du wieder was kochen?


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Vielleicht hilft dir ja auch eine Verbildlichung. Nehmen wir eine Küche.
> 
> Initial State q0 = Du bist in der Küche mit einem leeren Küchentisch
> Event b = du kochst etwas, q1 = es steht Essen auf dem Tisch
> ...


----------



## MoxxiManagarm (9. Apr 2019)

Der Graph den du gerade gezeigt hast, der gehört zu 1.3 nicht zu 1.2

Edit: Das Küchenbeispiel was du zitiert hast gehört aber zu 1.2


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Der Graph den du gerade gezeigt hast, der gehört zu 1.3 nicht zu 1.2


Oh hahaaha ist der dann richtig


----------



## MoxxiManagarm (9. Apr 2019)

Für 1.3 wäre m.E. der Graph aus dem letzten Bild richtig ja.

Edit: Nicht ganz, der Akzeptanzstatus fehlt.


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Für 1.3 wäre m.E. der Graph aus dem letzten Bild richtig ja.
> 
> Edit: Nicht ganz, der Akzeptanzstatus fehlt.


Die 0 gilt als Endstan.
Also bei q0


----------



## MoxxiManagarm (9. Apr 2019)

Richtig.


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Richtig.


Glaube jetzt hab ich das verstanden☺️


----------



## mihe7 (9. Apr 2019)

Heyoka955 hat gesagt.:


> Glaube jetzt hab ich das verstanden☺


----------



## MoxxiManagarm (9. Apr 2019)

Heyoka955 hat gesagt.:


> Glaube jetzt hab ich das verstanden☺


Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen 

{ w | w *∈* {a, b}*, sowohl a als auch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
{ w | w *∈* {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
{ w | w *∈* {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände


----------



## Heyoka955 (9. Apr 2019)

Also aber man muss am Anfang lange nachdenken.
Ich gehe folgend ran, ich mache Beispiel für die Wörter die fink


MoxxiManagarm hat gesagt.:


> Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen
> 
> { w | w *∈* {a, b}*, sowohl a als auch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
> { w | w *∈* {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
> { w | w *∈* {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände


werde ich machen wenn ich Zeit fidne. Aber die ersten beiden sind machbar.
Ich muss nachhause und erstmal Sport und Dann eine Programmier Aufgabe Lösen.


----------



## Heyoka955 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen
> 
> { w | w *∈* {a, b}*, sowohl a alsauch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
> { w | w *∈* {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
> { w | w *∈* {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände


Zu a muss man folgendes betrachten,

Wiir dürfen maximal aa oder bb.
Das heißt der erste q muss drei Pfeile haben einmal zu sich selbst also a einmal dann wieder a zum nächsten und dann dritte Pfeil b zum anderen.
Das heißt jedes q hat drei Möglichkeiten mit den Pfeilen.
Also sorry bin unterwegs


----------



## Heyoka955 (9. Apr 2019)

Hier zu. 1


----------



## mihe7 (9. Apr 2019)

Erklär doch mal, wie Du mit Knoten, die sich selbst referenzieren, ein Maximum erreichst.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Erklär doch mal, wie Du mit Knoten, die sich selbst referenzieren, ein Maximum erreichst.


Keine Ahnung ich habe die Aufgabe intuitiv gemacht. Wir sind nicht sehr weit beim
Thema. Wie meinst du Maximum?


----------



## Xyz1 (9. Apr 2019)

MoxxiManagarm hat gesagt.:


> Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen
> 
> { w | w *∈* {a, b}*, sowohl a als auch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände


@MoxxiManagarm Hatte gerad etwas Lw. :



(q1 == q0 == Startzustand  )


----------



## mihe7 (9. Apr 2019)

q1, q2, q4, q5 = aaba

EDIT: oops verlesen.


----------



## Xyz1 (9. Apr 2019)

mihe7 hat gesagt.:


> oops verlesen


Soo geht's aber nicht.


----------



## mihe7 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> Soo geht's aber nicht.


Aber, aber. oder "aba", "aba", um beim Thema zu bleiben - klar geht das  Und Dein Automat auch.


----------



## Heyoka955 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> @MoxxiManagarm Hatte gerad etwas Lw. :
> 
> Anhang anzeigen 11660
> 
> (q1 == q0 == Startzustand  )


wie sollte man bei so einer aufgabe vorgehen?
kann es sein dass es mehrere Automaten geben kann?


----------



## Xyz1 (9. Apr 2019)

Heyoka955 hat gesagt.:


> kann es sein dass es mehrere Automaten geben kann


Ne, andere Anordnungen und mehr Zustände => klar, aber dieser ist schon "zusammengefasst" 



Heyoka955 hat gesagt.:


> wie sollte man bei so einer aufgabe vorgehen


Es gibt eigentlich kein Schema F, aber vielleicht ein paar Tricks, frage mal @MoxxiManagarm ....


----------



## Heyoka955 (9. Apr 2019)

Tobias-nrw hat gesagt.:


> Ne, andere Anordnungen und mehr Zustände => klar, aber dieser ist schon "zusammengefasst"
> 
> 
> Es gibt eigentlich kein Schema F, aber vielleicht ein paar Tricks, frage mal @MoxxiManagarm ....


kann mir einer bei der aufgabe 2.3 helfen?


----------



## mihe7 (9. Apr 2019)

Heyoka955 hat gesagt.:


> Wie meinst du Maximum?


Es soll ein Buchstabe maximal n-mal vorkommen. 



Heyoka955 hat gesagt.:


> wie sollte man bei so einer aufgabe vorgehen?


Denken - auch wenn's schwer fällt.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Es soll ein Buchstabe maximal n-mal vorkommen.
> 
> 
> Denken - auch wenn's schwer fällt.


irgendwann kommt man darauf. aber was ist mit der anderen aufgaben


----------



## mihe7 (9. Apr 2019)

Nachdenken, probieren, verwerfen, nachdenken - das ist der Prozess. Das fällt schwer und mit der Zeit und wachsender Erfahrung wird es natürlich leichter, aber da musst Du durch.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Nachdenken, probieren, verwerfen, nachdenken - das ist der Prozess. Das fällt schwer und mit der Zeit und wachsender Erfahrung wird es natürlich leichter, aber da musst Du durch.


ist die Idee den richtig? für mich wirkt es richtig


----------



## Xyz1 (9. Apr 2019)

Und arbeite etwas an Deinem Schriftbild


----------



## mihe7 (9. Apr 2019)

Heyoka955 hat gesagt.:


> ist die Idee den richtig? für mich wirkt es richtig


Beweise es.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Beweise es.


----------



## mihe7 (9. Apr 2019)

Kein Video, eine Begründung von Dir - die Herleitung. Was hast Du gemacht usw.?


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Kein Video, eine Begründung von Dir - die Herleitung. Was hast Du gemacht usw.?


Nea ist ja selbstverständlich. aber von Dfa ist also ,am schaut von wo man anfängt nachem das man gemacht hat muss man von der Tabelle die werte für die einzelnen mengen einsetzten und gucken wohin der weg führt und wenn man das gemacht hat dann übernimmt man für den nächsten zustand.


----------



## Heyoka955 (9. Apr 2019)

mihe7 hat gesagt.:


> Kein Video, eine Begründung von Dir - die Herleitung. Was hast Du gemacht usw.?


bei nea müssen wir achten ob also wir fangen beu q0 an und schauen uns wann wo wir hingehen können falls a erscheint. Wnn dies der fall ist dann schreiben wir all emengen zu dem er hingehen kann, also in dem falle wäre das qo(zu sich selber) und q1 und q2. und dann schauen wir bei b und da gibt es keine kante dazu.
Nachdem wir das gemacht haben, schauen wir uns q1 an und gucken was passiert wenn a kommt und da passiert nix und wenn b eintritt geht er zurück zu q0. Und bei q2 ist das gleiche wie q0 denn er kann zu sich selber und zu q0 und bei kommt kein Ergebnis.


----------



## mihe7 (10. Apr 2019)

Dein letzter Kommentar ist schon viel besser als der vorletzte. Du beginnst also beim einzigen Startknoten des NFA und übernimmst ihn in den DFA. Im NFA erreichst Du mit einem a die Zustände q0, q1 und q2. Daher fasst Du diese zu einem neuen Zustand {q0, q1, q2} (kurz: q0q1q2) zusammen und hast im DFA einen Übergang (q0, a, q0q1q2). Für b gibt es von q0 aus keinen Zustandsübergang.

Soweit habe ich Dich verstanden und das ist auch korrekt. Beim Rest ist mir allerdings nicht klar, was Du da betreibst. Da fehlt mir der Zusammenhang zum DFA.


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Dein letzter Kommentar ist schon viel besser als der vorletzte. Du beginnst also beim einzigen Startknoten des NFA und übernimmst ihn in den DFA. Im NFA erreichst Du mit einem a die Zustände q0, q1 und q2. Daher fasst Du diese zu einem neuen Zustand {q0, q1, q2} (kurz: q0q1q2) zusammen und hast im DFA einen Übergang (q0, a, q0q1q2). Für b gibt es von q0 aus keinen Zustandsübergang.
> 
> Soweit habe ich Dich verstanden und das ist auch korrekt. Beim Rest ist mir allerdings nicht klar, was Du da betreibst. Da fehlt mir der Zusammenhang zum DFA.


also bei dfa ist die erste zeile und zweite zeile richtig? oder wie verstehe ich die aussage


----------



## mihe7 (10. Apr 2019)

Das kann sein, ich kann das Gekritzel nicht entziffern.

Bis jetzt haben wir nur einen Übergang (eine Kante), nämlich für a von q0 nach q0q1q2.


```
a
q0 --------> q0q1q2
```

Wie geht es jetzt weiter? Bei Deiner Erklärung oben fehlt noch was (ich meine, dass es in Deinem Bild vorhanden ist).


----------



## Heyoka955 (10. Apr 2019)

bei b muss leeres menge rauskommen


----------



## mihe7 (10. Apr 2019)

Das hatten wir ja schon: von q0 aus gibt es für b keinen Übergang (also keine Kante im Graphen).


----------



## Heyoka955 (10. Apr 2019)

dann gibt es nix meiner Meinung nach bei q0 in dfa wir können dann zur q0q1q2 als zustand also so


                          a                                                                                                                     b
q0q1q2     für a müssen wir gucken wohin q0 hingeht wenn a kommt 
                 und dann müssen wir gucken wohin q1 hingeht bei a 
                  und dann  q2. und diese mengen schreiben wir auf


----------



## mihe7 (10. Apr 2019)

EDIT: Überschneidung mit Deinem Post.


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> EDIT: Überschneidung mit Deinem Post.


ja eber ich sehe mein Problem nicht mehr.


----------



## mihe7 (10. Apr 2019)

Heyoka955 hat gesagt.:


> q0q1q2 für a müssen wir gucken wohin q0 hingeht wenn a kommt
> und dann müssen wir gucken wohin q1 hingeht bei a
> und dann q2. und diese mengen schreiben wir auf


Genau. Du schaust im DFA den nächsten Zustand an, hier also q0q1q2. Dieser beschreibt ja die Zustandsmenge {q0,q1,q2} im NFA. Daher schaust Du Dir im NFA für jeden dieser Zustände die Übergänge für a (und später für b) an.

Im NFA kommst Du von q0 aus mit einem "a" wieder zu {q0, q1, q2}. [EDIT: der Vollständigkeit halber sei erwähnt, dass es keine Kante für a von q1 aus gibt, und für q2 folgen die Zustände {q0,q2}. Insgesamt hat man also {q0, q1, q2}] Im DFA gibt es daher einen Übergang von q0q1q2 nach q0q1q2 für ein a.


```
a
                 +----+
                 |    |
       a         v    |
q0 --------> q0q1q2 --+
```

Wie sieht es bei b aus?


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Genau. Du schaust im DFA den nächsten Zustand an, hier also q0q1q2. Dieser beschreibt ja die Zustandsmenge {q0,q1,q2} im NFA. Daher schaust Du Dir im NFA für jeden dieser Zustände die Übergänge für a (und später für b) an.
> 
> Im NFA kommst Du von q0 aus mit einem "a" wieder zu {q0, q1, q2}. [EDIT: der Vollständigkeit halber sei erwähnt, dass es keine Kante für a von q1 aus gibt, und für q2 folgen die Zustände {q0,q2}. Insgesamt hat man also {q0, q1, q2}] Im DFA gibt es daher einen Übergang von q0q1q2 nach q0q1q2 für ein a.
> 
> ...


wäre dann das {q0}


----------



## mihe7 (10. Apr 2019)

```
a
                 +----+
                 |    |
       a         v    |
q0 --------> q0q1q2 --+
   <--------
       b
```
Da es jetzt im DFA keine Zustände gibt, die noch nicht betrachtet wurden, bist Du fertig.


----------



## Heyoka955 (10. Apr 2019)

also wie zeichen ich das ? meine Tabelle sieht so aus


----------



## mihe7 (10. Apr 2019)

In der linken Spalte hast Du die Startknoten (der Kanten) und in den rechten Spalten die Zielknoten der Kanten für a bzw. b.


----------



## Heyoka955 (10. Apr 2019)

hier


----------



## mihe7 (10. Apr 2019)

Da fehlt eine Kante...


----------



## Heyoka955 (10. Apr 2019)

Q0 zu sich selber


----------



## MoxxiManagarm (10. Apr 2019)

> > Heyoka955 hat gesagt.:
> > wie sollte man bei so einer aufgabe vorgehen
> 
> 
> Es gibt eigentlich kein Schema F, aber vielleicht ein paar Tricks, frage mal @MoxxiManagarm ....



Hmpf, meine Tipps habe ich doch schon gegeben  Für solche Aufgaben wir in Aufgabe 1 muss man sich "einfach" nur logisch überlegen was die möglichen Zustände sind, was diese bedeuten und was passiert wenn Event a oder b in diesem Zustand eintritt. q0-n sowie a und b sind mehr oder weniger nur "Platzhalter" für Zustandsbeschreibungen und Aktionen. Du könntest in jeden Kreis auch einen zustandsbeschreibenden Text schreiben und statt a und b das Event benennen.

Überspitzte Darstellung des Küchenbeispiels...


Frage an Heyoka zum Nachdenken: Was würde sich an diesem Diagram ändern wenn man die Prämisse ergänzt man will kein Essen auf dem Tisch vergammeln lassen.

Und das Schema für meine erste Übungsaufgabe von Tobias ist richtig. Mein Graph in der "Musterlösung" ist zwar anders angeordnet würde aber auf das Gleiche hinauslaufen. Ich hatte noch 2 weitere Übungsaufgaben ergänzt, falls du nochmal Langeweile bekommst


----------



## mihe7 (10. Apr 2019)

@Heyoka955 


mihe7 hat gesagt.:


> Da es jetzt im DFA keine Zustände gibt, die noch nicht betrachtet wurden, bist Du fertig.


Da war ich etwas zu voreilig: die akzeptierenden Zustände musst Du natürlich noch ermitteln. Das sind gerade die Zustände im DFA, deren Zustandsmenge im NFA (also z. B. {q0,q1,q2}) einen akzeptierenden Zustand enthält.


----------



## mihe7 (10. Apr 2019)

Heyoka955 hat gesagt.:


> Q0 zu sich selber


Ach @Heyoka955, wir haben doch von Anfang bis zum Schluss den kompletten Graphen konstruiert. Wie um alles in der Welt kommst Du jetzt darauf, dass es plötzlich einen Übergang von q0 zu sich selber geben sollte?


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Ach @Heyoka955, wir haben doch von Anfang bis zum Schluss den kompletten Graphen konstruiert. Wie um alles in der Welt kommst Du jetzt darauf, dass es plötzlich einen Übergang von q0 zu sich selber geben sollte?


Du hast gesagt dass eine Kante fehlt. Und da q0 zu sich selber geht dachte ich die wäre diese jedoch habe ich geschaut und auch gemerkt macht sich kein Sinn da q0 zu sich selber in dem
Anderen Zustand schon steht.

Also es fehlt nur eine Kante vielleicht würde ich sagen q0q1q2 zu sich selber weil wir in der Tabelle gesehen haben dass von
Dort aus zu sich selber nochmal geht ?


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Ach @Heyoka955, wir haben doch von Anfang bis zum Schluss den kompletten Graphen konstruiert. Wie um alles in der Welt kommst Du jetzt darauf, dass es plötzlich einen Übergang von q0 zu sich selber geben sollte?


Du meintest ja dass eine Kante fehlt ?


----------



## mihe7 (10. Apr 2019)

Ja, Du hast vergessen, eine Kante einzuzeichnen. Die Konstruktion des Automaten ist vollständig.


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Ja, Du hast vergessen, eine Kante einzuzeichnen. Die Konstruktion des Automaten ist vollständig.


Welche Kante ist das?


----------



## mihe7 (10. Apr 2019)

Zähl halt mal alle Kanten aus der Konstruktion auf, ansonsten vgl. Bild aus Kommentar #89.


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Zähl halt mal alle Kanten aus der Konstruktion auf, ansonsten vgl. Bild aus Kommentar #89.


Habe ich, sowie es aussieht brauche Ich für {q0} leere Menge


----------



## MoxxiManagarm (10. Apr 2019)

Heyoka955 hat gesagt.:


> Habe ich, sowie es aussieht brauche Ich für {q0} leere Menge


Du hast in deinem Kommentar #90 doch die Tabelle aufgezeichnet. Die war korrekt.


ab{q0}*{q0,q1,q2}**{Ø}{q0,q1,q2}**{q0,q1,q2}***{q0}*

Das sind genau 3 Kanten, in der Tabelle hervorgehoben. In #92 hast du eine davon nicht eingezeichnet. Eine Kante zur leeren Menge muss nicht eingezeichnet werden. @mihe7's Graph aus #89 war bereits vollständig.


----------



## mihe7 (10. Apr 2019)

@MoxxiManagarm Danke.


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> ```
> a
> +----+
> |    |
> ...


Ich verstehe dieses v und plus nicht ?


----------



## Robat (10. Apr 2019)

Heyoka955 hat gesagt.:


> Ich verstehe dieses v und plus nicht ?


Nicht dein Ernst, oder?


----------



## MoxxiManagarm (10. Apr 2019)

Heyoka955 hat gesagt.:


> Ich verstehe dieses v und plus nicht ?


Alter... @mihe7 hat den Graph nunmal in Ascii gezeichnet. Das v ist nur eine Pfeilspitze und die + sind Knicke , die haben nichts weiter zu bedeuten. Insgesamt sind das nur Kanten.


----------



## Heyoka955 (10. Apr 2019)

Robat hat gesagt.:


> Nicht dein Ernst, oder?


Ich studiere erst seit einem Jahr.
Ihr könnt doch nicht erwarten daas ich alles verstehe  haha


----------



## MoxxiManagarm (10. Apr 2019)

Dennoch tust du dich insgesamt extrem schwerfällig. Aber eins muss man dir lassen - du bist hartnäckig.


----------



## mihe7 (10. Apr 2019)

Heyoka955 hat gesagt.:


> Ich studiere erst seit einem Jahr.
> Ihr könnt doch nicht erwarten daas ich alles verstehe  haha


Kann es sein, dass Du in Wahrheit Soziologie studierst und hier einen Test "wie treibe ich die Massen in den Wahnsinn" durchführst? haha


----------



## Heyoka955 (10. Apr 2019)

mihe7 hat gesagt.:


> Kann es sein, dass Du in Wahrheit Soziologie studierst und hier einen Test "wie treibe ich die Massen in den Wahnsinn" durchführst? haha


Lol Hahahhas


----------

