Automaty skończone deterministyczne i nie-

Dla specjalistów Programowanie
#1

a teraz troszkę inna struktura danych

image_id: 2447

mam taki automat, który jest automatem niedeterministycznym akceptującym wszystkie łańcuchy zawierające przynajmniej jedną parę kolejnych zer lub jedynek i pytania czy ciągi słów

-01100

-1000010

-1100

-000

są akceptowane przez ten automat ?

no i teraz moje pytanie jest takie, bo np. pierwsze słowo wygeneruje się do postaci 011 i po wygnerowaniu ostatniej 1 będzie już w q2 który jest stanem końcowym i automat się zakończy, prawda ? a słowo nie zostanie wygenerowane… czy może się mylę ?

#2

Te twoje rozważania byli by poprawne dla automatu deterministycznego.

Przedstawiony automat niedeterministyczny najprościej zrozumieć następująco.

Ponieważ q0 ma do samego siebie jedynki i zera to ignorujemy na początku dowolną ilość jedynek i zer

Ponieważ q2 ma do samego siebie jedynki i zera to ignorujemy po q2 dowolną ilość jedynek i zer

Ponieważ q4 ma do samego siebie jedynki i zera to ignorujemy po q4 dowolną ilość jedynek i zer

więc mamy jedno z dwóch:

  • na początku cokolwiek, potem 00, reszta ignorowana

  • na początku cokolwiek, potem 11, reszta ignorowana

Podsumowując: jeżeli ciąg słów zawiera 00 lub 11 to znaczy że ten ciąg akceptowany przez ten automat ?

#3

to wychodzi, ze wszystkie są akceptowane

– Dodane So sty 30, 2010 9:32 pm –

a jakby np. w stanach końcowych nie było pętli ?

#4

Add 01100

q0 -> 0 -> q0 -> 1 -> q1 -> 1 -> q2 -> 0 -> q0 -> 0 > q0

Add 1000010

q0 -> 1 -> q0 -> 0 -> q0 -> 0 -> q3 -> 0 -> q4 -> 0 > q4 -> 1 -> q4 -> 0 -> q4

etc.

Co do pytania co by było gdyby nie było strzałek na końcowych stanach. Wtedy albo można “skonsumować” ciąg we wcześniejszych stanach albo ciągu nie da się wygenerować tego ciągu. (Podane przez ciebie ciągi da się wygenerować)

#5

a nie będzie tak jak usunąć skierowania ze stanów końcowych, że np. drugie słowo nie będzie akceptowane ?

#6

Dokładnie tak będzie.

#7

czyli jeśli automat, inaczej, jeśli automat dojdzie jakąś etykietą przejścia do stanu końcowego i w tym stanie końcowym nie ma już pętli to się po prostu działania automatu kończy ?

czyli np, po odrzucenie pętli w stanach końcowych, słowo 1100 jest akcpetowane wciąż, ale już słowo 11001 nie będzie, a znowu słowo 00110 równiez nie będzie ?

#8

Nie mył automatów deterministycznych z niedeterministycznymi, automat niedeterministyczny nie może fizycznie działać, co najwyżej może sprawdzić czy podane słowo/wyraz/zdanie pasuje do niego czy też nie. Typowym automatem niedeterministycznym jest wzór regexp w PHP (i nie tylko) a wzór nie może działać. Natomiast sam komputer jest typowym automatem deterministycznym - może działać.

Przy odrzuceniu pętli końcowych automat będzie przyjmować/akceptować tylko słowa kończące się na 00 lub 11.

#9

Chyba, że się go zdeterminizuje (patrz: http://wazniak.mimuw.edu.pl/index.php?title=J%C4%99zyki%2C_automaty_i_obliczenia/Wyk%C5%82ad_6:_Automat_niedeterministyczny._Lemat_o_pompowaniu)

#10

image_id: 2451

ten automat słów 01011 oraz 110101 nie akceptuje, prawda ?

w pierwszy przypadku dojdzie do stanu końcowego na drodze q0-q2-q3-q1-q0 i tutaj koniec a słowo wygląda tak - 0101

w drugim przypadku do stanu końcowego dojdzie na drodze q0-q1-q0 a słowo będzie wyglądało tak 11

w obu przypadkach nie ma takiej ścieżki po której, w pewnym momencie, dało by się przejść aby wygenerować zadane słowo

ale słowo np. 10001110 już będzie akceptowane na drodze q0-q1-q3-q1-q3-q2-q3-q2-q0, tak ?

no i jest to automat deterministyczny, bo przy jednej etykiecie przejścia można przejść tylko do jednego węzła, tak ?

#11

01011 = q0->q2->q3->q1->q0 ->q1 = automat nie jest w stanie końcowym = nie zaakceptowano

110101 = q0->q1->q0 ->q2->q3->q1->q0 = automat jest w stanie końcowym = zaakceptowano

10001110 = q0->q1->q3->q1->q3->q2->q3->q2->q0 = automat jest w stanie końcowym = zaakceptowano

automat deterministyczny.

Nie wiem czemu uważasz że automat zatrzyma się przy pierwszym powrocie do q0, nie zatrzyma się - działa dalej.

#12

[alex],

no bo doszedł do stanu końcowego, stan końcowy to stan końcowy… a czemu może badać zadane słowo ten automat dalej, mimo dojścia już do stanu końcowego ?

#13

Ponieważ stan końcowy (w odróżnieniu od stanu początkowego) nie jest częścią automatu, stanów końcowych może być więcej niż jeden, właściwie wszystkie węzły naraz mogą być stanami końcowymi (początkowy zawsze tylko jeden).

#14

i fakt, że są tutaj pętle pewnie ma znaczenie?

Bo bazując na tym co mówisz, słowo np.

1100 także będzie akceptowane przez automat, jak i równiez słowo 10101010, mimo że w obu tych słowach odwiedza stan końcowy dwukrotnie ?

#15

Stan się nazywa “końcowy”, ale to nie znaczy, że jeśli się go osiągnie to trzeba kończyć. W przypadku automatu deterministycznego, aby słowo było akceptowane, po wczytaniu go w całości musimy musimy znajdować się w stanie końcowym. To, które stany są końcowe, interesuje nas dopiero po przetworzeniu całego słowa.

#16

aha !.., czyli ważne jest tylko to, żeby po przetworzeniu jakiegolwiek słowa być w stanie końcowym ?

1010101 - czyli to słowo nie wejdzie, bo nie będę na po przetworzeniu ostatniej jedynki w q0 ?

#17

Zgadza się. Po poprawnym wczytaniu całego słowa, odpowiedź na pytanie “Czy słowo jest akceptowane?” jest równoważna odpowiedzi na pytanie “Czy automat znajduje się w którymś ze stanów końcowych?”.

#18

Automat nie może niepoprawnie wczytać słowa. Zawsze jest w jakimś stanie. Raczej już: - “Po wczytaniu całego słowa”.

#19

http://en.wikipedia.org/wiki/Finite-state_machine#Mathematical_model zobacz notkę o funkcji delta - wyraźnie tam stoi, że \delta(q, x) nie musi być zawsze określona - wtedy automat może przerwać działanie przedwcześnie. Naturalnie, można stworzyć stan niekońcowy q_{czarna dziura}, który łapie wszystko i się kręci w pętli, ale po co?

#20

flash4gordon , mylisz automat deterministyczny z implementacją automatu deterministycznego.