Computation Theorie - DFA

Question

Ich möchte ein DFA eines Alphabets entwerfen {x, y, z} die Worte mit einer Anzahl von ‚z‘ ein Vielfaches von 3 (zB „xzyyxzzyy“) jemand akzeptiert

Hat weiß, wie ? oder welche Sprache akzeptiert sie?

Answer 1

Sie drei Staaten benötigen Überblick über die Anzahl von z zu halten gesehen hat, Modulo drei; Die Zustände werden einander auf der Eingabe z durchlaufen, und die eine für #z (w) = 0 (mod 3) wird der einzige akzeptierende Zustand sein.

auf einem beliebigen x und Y den erlauben, jeder Zustand kann auf diesen Eingaben mich Schleife.

Sie könnten q0, q1 und q2 für die Staaten, so dass q0 den Anfangszustand und einzigen Staat zu akzeptieren verwenden. Dann haben Sie drei Übergänge f (qi, z) = wh mit j = i + 1 (mod 3), drei Übergänge f (q, x) = q und drei Übergänge f (q, y) = q für insgesamt neun Übergänge.