0 Daumen
680 Aufrufe

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

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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.


Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community