Automaten und Produktautomaten

Question

Seien A = (P, Σ, δA, p0, FA) = B = (Q, Σ, δB, q0, FB) endliche Automaten. Beweisen Sie induktiv, dass für den Produktautomaten A x B gilt:

∀w ∈ Σ* : δ* (AxB) ( (p,q),w) = (δ*(A) (p,w), δ*(B) (q,w) )

wir sollen jeden der Umformungsschritte begründen. Ohne einen Ansatz zu haben die Aufgabe so reinzustellen ist dreist aber ich komm nicht mehr weiter, da mir zu dieser Aufgabe absolut nichts einfällt. Wenn Ihr helft dann vielen dank und wenn nicht ist es verständlich.

LG

Answer 1

Vollständige Induktion über |w|.

IA: |w| = 1. Dann ist δ* (AxB) ( (p,q),w) = δ (AxB) ( (p,q),w) = (δ(A) (p,w), δ(B) (q,w) ) = (δ*(A) (p,w), δ*(B) (q,w) ) laut Definition von δ* und des Produktautomaten.

IV: Sei |w| = n+1 und δ* (AxB) ( (p,q),v) = (δ*(A) (p,v), δ*(B) (q,v) ) für jedes v ∈ Σ* mit |v| ≤ n.

IS: Selbst machen.