0 Daumen
37 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

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.


von 1,7 k  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...