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
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.
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos