Text erkannt:
Wir bezeichnen zwei Automaten \( \mathcal{A}_{1}, \mathcal{A}_{2} \) als fast äquivalent, wenn sie sich in der Akzeptanz bei nur endlich vielen Wörtern unterscheiden. D.h. es gibt nur endlich viele Wörter, für die \( w \in L\left(\mathcal{A}_{1}\right) \Leftrightarrow w \in L\left(\mathcal{A}_{2}\right) \) nicht gilt. Entwerfen Sie ein möglichst effizientes Verfahren, mit dem sich das folgende Problem entscheiden lässt: Gegeben zwei deterministische endliche Automaten \( \mathcal{A}_{1}, \mathcal{A}_{2} \), sind \( \mathcal{A}_{1} \) und \( \mathcal{A}_{2} \) fastäquivalent?
Problem/Ansatz:
