Czy są jakieś nieskończone automaty?

35

W teorii automatów wszyscy od samego początku czytamy automaty jako automaty skończone. Chcę wiedzieć, dlaczego automaty są skończone? Dla jasności, co to jest w skończonym automacie - alfabet, język, ciągi znaków wyrażeń regularnych, czy co? Czy istnieją (teoretycznie) jakieś nieskończone automaty?

parvin
źródło
1
Z pewnością nie język ani „ciągi znaków wyrażeń regularnych”; wiele prostych wyrażeń regularnych pasuje do nieskończonej liczby ciągów (ale można je rozpoznać po skończonym automacie.)
Alexis
Zadałem pytanie, mając na uwadze nieskończone
Words Like Jared

Odpowiedzi:

34

Wszystkie modele automatów, które zwykle napotykasz, są skończone; w przeciwnym razie byłoby ich niepoliczalnie wiele, co oznacza, że ​​nie są wychwyceni przez modele Turinga. Lub, zdaniem CS, byłyby bezużyteczne¹.

„Automaty skończone” są nazywane skończonymi, ponieważ mają tylko skończony zestaw konfiguracji (na bok ciąg wejściowy). Na przykład automaty wypychające mają stos, który może mieć dowolną treść - istnieje nieskończenie wiele możliwych konfiguracji.


Uwaga: Konfiguracje urządzeń PDA są nadal skończone! W rzeczywistości każdy model obliczeniowy, który mieści się w zakresie obliczalności Turinga, musi mieć konfiguracje w pełni reprezentowalne, w przeciwnym razie TM nie byłyby w stanie ich symulować.


  1. Świadomie pomijam tutaj hiper-obliczenia dla celów tego pytania.
Raphael
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Raphael
32

Pełna nazwa to „skończony stan automatów”. Najważniejsze jest to, że stan automatu może być w pełni scharakteryzowany przez element pewnego skończonego zbioru stanów dyskretnych. Oznacza to, że jeśli (odpowiedni) stan automatu obejmuje zmienną o wartości rzeczywistej, istnieje nieskończona liczba stanów potencjalnych (pomijając skończoność reprezentacji zmiennoprzecinkowych), a automat nie jest skończony.

Może się to nigdy nie zdarzyć w informatyce teoretycznej, ale nie jest to zbyt egzotyczne w dziedzinie modelowania sekwencji liczb rzeczywistych. Ukrytych modeli Markowa można użyć do modelowania sekwencji liczb jako danych wyjściowych układu probabilistycznego składającego się z jednego filtra wyjściowego dla każdego stanu (dyskretnego, skończonego) modelu Markowa ze stanami nieobserwowalnymi. Filtry obliczają następne dane wyjściowe o wartości rzeczywistej z wektora poprzednich wyników (model „autoregresyjny”), ale bazowy model Markowa jest skończony, ponieważ jego prawdopodobieństwa przejścia zależą tylko od aktualnego stanu Markowa.

Jednak w tym artykule ( pełny tekst ) opracowano odmianę, w której prawdopodobieństwo przejścia zależy również od wektora liczb rzeczywistych wcześniejszych wyników. Stan tego układu jest kombinacją dyskretnego stanu Markowa i krotki liczb rzeczywistych („model Markowa stanu mieszanego”), dlatego może być w nieskończonej liczbie różnych stanów.

Krótko mówiąc, automaty nieskończone są teoretycznie dobrze zdefiniowane, a czasem nawet spotykane.

Alexis
źródło
1
Pełne ujawnienie: jestem jednym z autorów wspomnianego artykułu. Nie jestem pewien, czy jest to uważane za właściwe ujawnienie czy nieistotną autopromocję ...
Alexis
6
Myślę, że w razie potrzeby można odwoływać się do własnej pracy - jeśli jesteś jednym z wiodących ekspertów w temacie, cieszymy się, że cię mamy! - i zwykłe ujawnienie, jak twoje, wystarczy. Dzięki!
Raphael
Automaty skończone nie obejmują automatów wypychających, prawda? Czy istnieje jakiś szczególny powód aż do stanów liczb rzeczywistych? Nie jestem pewien, czy coś mi brakuje w tym, dlaczego ten oczywisty przykład nie zadziała, czy po prostu przypadkiem wybrałeś niezwykły przykład.
Mehrdad
1
Myślę, że próbuje zapytać, dlaczego nie użyłeś bardziej konwencjonalnego nie-FSA, takiego jak automat pushdown, zamiast przeskakiwać do czegoś w rodzaju zmiennych stanu o wartościach rzeczywistych.
user2357112 obsługuje Monica
1
Cóż, głównie dlatego, że o tym pomyślałem! Ale także „stan” modelu Markowa ze stanem mieszanym składa się ze stałej liczby parametrów, ale wciąż istnieje nieskończona liczba stanów (definiowana jako pozycja aktualna + prawdopodobieństwa przejścia), ponieważ niektóre parametry są liczbami rzeczywistymi (ale wpływają na przejścia, nie tylko wyjście). W przypadku PDA niedokładność wynika z nieograniczonej wielkości stosu; ale wciąż istnieje tylko skończona liczba reguł, które mają skończoną długość, więc na jednym kroku jest tylko skończona liczba możliwych pszczół.
Alexis
19

W skończonym automacie jest dość skończoność: liczba stanów, rozmiar podstawowego alfabetu i długości ciągów znaków akceptowanych przez maszynę.

Z pewnością możesz złagodzić warunek skończoności, pozwalając, powiedzmy, maszynie mieć nieskończenie wiele stanów, ale jeśli tak, to wynikowa maszyna stanie się nieciekawa, w takim sensie, że takie maszyny mogą być zaprojektowane tak, aby w ogóle akceptować dowolny język.

Rick Decker
źródło
A co jeśli nieskończony jest tylko alfabet? co jeśli na przykład pracujemy z wyrażeniem regularnym na liczbach naturalnych? czy to jest możliwe?
parvin
8
Jeśli automat jest skończony, ale alfabet jest nieskończony, to automat będzie miał skończoną liczbę przejść z każdego stanu. Wszelkie znaki niezwiązane z jedną z przejść nie zostaną rozpoznane przez automat. W rezultacie możesz zastąpić nieskończony alfabet skończonym alfabetem zawierającym tylko znaki występujące w przejściach automatu, a automat nadal akceptuje dokładnie ten sam język.
Kevin - Przywróć Monikę
3
@parvin Nie bardzo. Potrzebowałbyś wtedy nieskończonej liczby przejść między (skończoną liczbą) stanami - których nadal nie możesz reprezentować. Jeśli wybierasz predykaty (np. „Wszystkie parzyste dane idą od A do B, wszystkie nieparzyste dane idą od A do C”), zasadniczo dzielisz alfabet na skończoną liczbę klas równoważności.
Bergi
@Kevin, to zależy od tego, jak zdefiniujesz „skończoną liczbę przejść”. Rozważmy zwykły (skończony) FSA z następnym stanem wybranym zgodnie z dowolnym skończonym podziałem liczb naturalnych: np. Przez pozostałą część dzielenia przez 7. Lub rozważmy podobną sytuację z udziałem liczb rzeczywistych. Diagram stanu jest w pełni skończony, ale jest dobrze zdefiniowany na nieskończonym alfabecie.
Alexis
@Parvin Powiedziałbym, że odpowiedź brzmi „tak” (patrz mój poprzedni komentarz).
Alexis,
10

W rzeczywistości w teorii automatów (która bardzo odbiega od początków Kleene, Rabina i Scotta) istnieje wiele form automatów, które nie są skończone. Wynika to z kilku powodów.

Na przykład automaty wypychające to automaty o nieskończonym zestawie konfiguracji (mają one skończoną liczbę stanów, ale w rzeczywistości należy je traktować jako „automaty nieskończone”).

Podobnie istnieją inne przykłady nieskończonych automatów, dla których przestrzeń stanu jest nieskończona, ale o dużej strukturze. Na przykład rozważa się klasę automatów, które mają jako przestrzeń stanu przestrzeń wektorową (wymiar skończony), a jako funkcje przejściowe mapy liniowe (plus niektóre rzeczy początkowe i końcowe). Są one znane jako automaty ważone nad polem bazowym (Schützenberger w 61). Można je zminimalizować i przetestować pod kątem równości. Inne przykłady obejmują automaty rejestrów ( automaty te mają skończony zestaw rejestrów i działają na nieskończonym alfabecie: mogą one porównywać litery z rejestrami i przechowywać litery w rejestrach) oraz bardziej nowoczesną formę automatów nominalnych (które mają tę samą ekspresję, ale mają lepsze podstawy i właściwości). Pustka takich automatów jest rozstrzygalna.

Ale nawet w przypadku badania automatów skończonych sensowne jest mówienie o automatach nieskończonych. Rzeczywiście, rozważmy kategorię automatycznych deterministycznych automatów skończonych, które akceptują ustalony dany język L, wyposażonych w standardowe pojęcie morfizmu automatów, wtedy kategoria ta nie ma obiektu początkowego i końcowego. Jeśli jednak mieszkasz w kategorii wszystkich deterministycznych (powiedzmy policzalnych) automatów, istnieje obiekt początkowy (automat, który ma jako stanyZA, jako początkowy stan puste słowo, gdy czyta literę za uroczyście u idzie do stanu uza, a stan akceptuje, jeśli należy do L). Istnieje również końcowy obiekt (który ma jako stan języki!). Istnienie tych dwóch obiektów jest jednym ze sposobów wyjaśnienia na wysokim poziomie, dlaczego deterministyczne automaty można zminimalizować i są ściśle powiązane z przystawką Myhill-Nerode.

Podsumowując, istnieją automaty nieskończone, ale modele, które są najpierw badane na wykładzie, są zawsze stanami skończonymi.

Thomas Colcombet
źródło
2

Myślę, że pytanie zakłada, że ​​nie ma automatów o nieskończonym stanie, gdy są, po prostu nie warto ich wychowywać.

W teorii automatów istnieje hierarchia uprawnień różnych modeli wirtualnych. Ten, którego się nauczyłem, miał 4 (pamiętam, że minęło już trochę czasu), ten, który znalazłem na Wikipedii, ma 5. Najsłabszy w obu automatach skończonych, a najsilniejszy to maszyny Turinga. Istnieje pewna koncepcja poziomu potężniejszego niż maszyny Turinga, który nazywa się luźno hiperkomputacją. Wiele różnych opisów maszyn wirtualnych należy do jednego z tych poziomów. Maszyny Turinga są szczególnie znane z wielu modeli o tym samym poziomie mocy obliczeniowej.

Automaty nieskończonego stanu, przynajmniej jeden formalnie zdefiniowany, spadną na jeden z tych poziomów. Może być coś interesującego w pokazaniu, jak pewna rygorystyczna definicja automatów nieskończonego stanu mieści się w jednym z tych poziomów, ale poza tym nie byłaby przydatna, biorąc pod uwagę, że o wiele lepiej zbadane maszyny wirtualne reprezentują każdy poziom . Jest podobny do tego, jak mało jest zainteresowania maszyną Turinga o miliardach taśm, ponieważ nie byłaby ona mocniejsza niż pojedyncza maszyna Turinga, ale bardziej skomplikowana w obsłudze.

Jeśli zdarzyło Ci się znaleźć nieskończone automaty stanów, które nie były równoważne z istniejącym poziomem hierarchii, może to być interesujące. Ale bez tego automaty stanów nieskończonych są już przechwytywane w ramach istniejącej hierarchii, a biorąc pod uwagę dodatkowe komplikacje związane z radzeniem sobie z nieskończonością, po prostu ich unikamy w taki sam sposób, jak unikamy nadmiernie skomplikowanych modeli maszyn Turinga.

Lawtonfogle
źródło
2

(Naiwna) nieskończona wersja deterministycznej maszyny skończonej jest zbyt potężna . Taka rzecz mogłaby w ogóle „zapamiętać” dowolny język, więc nie można się wiele z tego nauczyć.

Na przykład nad binarnym alfabetem rozważ automat w postaci pełnego drzewa binarnego o nieskończonej wysokości. Każdy możliwy ciąg znaków, który można traktować jako dane wejściowe, odpowiada jednoznacznie węzłowi drzewa, dzięki czemu można zbudować decydujący dla dowolnego języka, po prostu tworząc odpowiednie węzły akceptujące stany.


źródło