Wersja z 04:57, 31 maj 2012 edytuj Cardel (dyskusja \| edycje) 548 edycji Nie podano opisu zmian ← poprzednia edycja		Wersja z 05:31, 31 maj 2012 edytuj anuluj edycję Cardel (dyskusja \| edycje) 548 edycji Nie podano opisu zmian następna edycja →
Linia 1: Do [[Determinizacja automatu skończonego]] == ~~Metoda~~Opis metody == Determinizacja [[niedeterministyczny automat skończony\|niedeterministycznego automatu skończonego]] <math>N</math> polega na konstrukcji [[deterministyczny automat skończony\|deterministycznego automatu]] <math>D</math>, który będzie symulował działanie <math>N</math>. Automat <math>D</math> po każdym przejściu pamięta zbiór wszystkich stanów, które <math>N</math> mógłby osiągnąć w danym kroku. Jeżeli po zakończeniu działania ten zbiór zawiera jakikolwiek stan akceptujący, przeczytane słowo jest akceptowane. ~~Stany D to zbiory stanów N. W każdym kroku po przeczytaniu znaku a D przyjmuje stan odpowiadający zbiorowi stanów, który automat N przyjąłby w odpowiadającym kroku.~~ == ~~Formalizm~~Formalna konstrukcja == Niech <math>N=(Q_N,f_N,q_0,F_N)</math> nad alfabetem <math>\Sigma</math> będzie ~~NAS~~automatem niedeterministycznym o zbiorze stanów <math>Q_N</math>, funkcji przejść <math>f_N:\Sigma \rightarrow \mathcal{P}(Q_N)</math>, stanie początkowym <math>q_0</math> i zbiorze stanów akceptujących <math>F_N</math>. Wtedy automat <math>D=(Q_D,f_D,\{q_0\},F_D)</math> ~~jest~~zdefiniowany w ~~DAS~~następujący sposób: * <math>Q_D = \mathcal{P}(Q_N)</math> * <math>f_D: Q_D \times \Sigma \ni (S,a) =\rightarrow \bigcup_{s \in S}f_N(s,a) \in Q_D</math> * <math>F_D = \{S \in \mathcal{P}(Q_N): S \cap F_N \neq \emptyset\}</math> jest deterministyczny i akceptuje ten sam język co <math>N</math>.

Wikipedysta:Cardel/brudnopis: Różnice pomiędzy wersjami