Czy FSA może się liczyć?

To może być głupie pytanie. Wydaje się jasne, że FSA, ponieważ jest skończona, może zliczyć tylko liczbę symboli w ciągu wejściowym do liczby ograniczonej liczbą stanów. Ale teraz załóżmy, że wyposażamy FSA w funkcje wyjściowe (np. Drukowanie). Byłoby wówczas bardzo łatwo zbudować maszynę zdolną do drukowania jednego symbolu dla każdego odczytywanego symbolu. Czy liczyłoby to jako liczenie? Jeśli nie, dlaczego nie?

Ujmując to w kategoriach FST: Rozumiem, że nie jest możliwe zbudowanie FST zdolnego do odwzorowania ciągu o dowolnej długości na reprezentację binarną (tj. Liczbę w systemie liczbowym base-2) o jego długości. Ale jest oczywiście trywialne skonstruowanie FST zdolnego do mapowania ciągu o dowolnej długości na ciąg zer zerowych (lub zer) o tej samej długości. Ale to może się liczyć jako liczenie, czyż nie, ponieważ to, co robi FST, polega na budowaniu reprezentacji długości jego danych wejściowych. Nieco dziwna reprezentacja, ale nadal reprezentacja, prawda?

To pytanie jest nieco niejasne, więc tutaj jest niejasna odpowiedź: Tłumaczenie jednoargumentowego na jednoargumentowy nie jest dokładnie liczone, ponieważ maszyna tak naprawdę nie „wie”, jaki rozmiar danych wejściowych był „na końcu”.

Zdajesz sobie z tego sprawę, dlatego kwestionujesz fakt, że to naprawdę się liczy.

Tłumaczenie z jedności na binarnie wydaje się jednak znacznie bardziej zaawansowaną operacją, ponieważ obejmuje nie tylko liczenie, ale także arytmetykę.

Być może więc bardziej precyzyjne pojęcie, na które należy patrzeć, zamiast liczyć, jest porównywanie . To znaczy, biorąc pod uwagę dwie liczby (w jedności) i , określ, czy .1 m n = $1^n$$1^m$$n=m$

Możliwość wykonania tego porównania daje początek słynnemu nieregularnemu językowi . A niemożność policzenia przez NFA sprawia, że ​​ten język jest nieregularny.$\{a^nb^n: n\ge 0\}$

Co ciekawe, tym językiem jest CFL. I rzeczywiście, odpowiedni model automatów - PDA, ma możliwość wykonania ograniczonego porównania.

Kiedy mówimy o porównywaniu, przetworniki nie dają już żadnej dodatkowej mocy, więc pytanie zostało rozwiązane w tym sensie.

Dodatkowa uwaga: całkowicie nieformalnie, możliwość porównania dwóch liczb może być często wykorzystana do symulacji 2-licznikowej maszyny Minsky Machine , która jest odpowiednikiem TM.

Nie. Automaty skończone nie liczą się. Mogą robić rzeczy, które wyglądają tak, ale nie mogą liczyć. Mogą nawet wykonywać małe (na stałe) obliczenia (takie jak ustalenie, czy liczba binarna jest podzielna przez trzy ), ale to się nie liczy.

Trochę historii. Jesteś na dużym prostokątnym placu w słynnym mieście. Miejscowi mówią, że kwadrat jest w rzeczywistości kwadratowy. Jeśli możesz policzyć, sprawdź, czy pozioma i pionowa liczba płytek się zgadza, licząc płytki wzdłuż boków kwadratu. Jeśli nie możesz liczyć, możesz zweryfikować roszczenie: zacznij od rogu i idź po przekątnej. Jeśli dokładnie dojdziesz do przeciwległego rogu, masz kwadrat.

W przykładzie testy FSA czy ciąg ma równą liczbę „s oraz ” s poprzez liczenie tych liczb do dwóch różnych taśm wyjściowych. Inne urządzenie musi być robi ostateczną porównania, chyba że masz trick do obsługi listów i w parach i cros przy jednej z drugą. Jak na placu.b a $a$$b$$a$$b$

Teraz bardziej formalny model do porównania. Według twierdzenia Chomsky'ego-Schützenbergera każdy bezkontekstowy język jest odwrotnością skończonej transdukcji stanu języka Dyck na dwóch parach nawiasów (nie jest tak powiedziane na wikipedii, ale musisz mi uwierzyć). Teraz przetwornik skończonego stanu może „zaakceptować” swój bezkontekstowy język w następujący sposób (dla każdego języka własny przetwornik). Na wejściu przekształca ciąg znaków na (odgadnięte) serie trzasków i wypychań pda dla , a następnie przetestuj, czy wynikiem jest zachowanie w dół, tzn. Wynik jest ciągiem wT D 2 L = T - 1 ( D 2 ) T L T L D 2 w ∈ T - 1 ( D 2 ) T ( w ) ∈ D $L$$T$$D_2$$L = T^{-1}(D_2)$$T$$L$$T$$L$$D_2$ . (Szczegóły techniczne zostały pominięte, ale twierdzenie Ch-Scha twierdzi: jeden ma iff )$w\in T^{-1}(D_2)$$T(w) \in D_2$

Chodzi mi o to, że przetwornik wykonuje pewne „obliczenia”, ale w teście z ukryta jest duża moc . Podobnie twój przykład, w którym dwie litery są posortowane na dwóch taśmach. $D_2$

@Shaull: Dzięki za odpowiedź! Jestem nowy w StackExchange i nie wiem, jak skomentować odpowiedź, więc zamiast tego zdecydowałem się napisać odpowiedź w nadziei, że mi wybaczą.

Hmm, wydaje mi się, że liczy się owczarek liczący swoje owce, pisząc znak na kartce papieru dla każdej owcy, którą widzi, lub więzień liczący dni, w których przebywał w więzieniu, pisząc znaki na ścianie. Dlaczego n znaków na kartce papieru lub na ścianie nie liczy się jako reprezentacja liczby n? Czy to nie jest tak zwana reprezentacja Tally? AFAICS nie jest w żaden oczywisty sposób gorsza od (powiedzmy) reprezentacji binarnej, poza tym, że zajmuje więcej miejsca.

Sądzę więc, że dla ciebie „wiedzieć” oznacza, że ​​ma ona wewnętrzną reprezentację liczby na końcu. Wtedy oczywiście jest oczywiste, że FSA z FST nie może obliczyć długości dowolnego ciągu. Ale jeśli nie wymagamy wiedzy w tym sensie, ale wymagamy tylko, aby FSA lub FST były w stanie przekazać wynik zewnętrznemu obserwatorowi, to wydaje mi się, że przedstawienie liczby w formacie tally powinno być w porządku.

Ponadto, jeśli FSA jest wyposażony zarówno w inkrementalne wejście jak i wyjście, to w zasadzie powinien być w stanie wykorzystywać swoje środowisko zewnętrzne jako pamięć do odczytu / zapisu, a tym samym być tak potężny jak maszyna Turinga. Dobrze?

Dzięki za poruszenie problemu porównania. Teraz wydaje się, że jeśli zniesiemy wymóg wewnętrznej reprezentacji i wymagamy jedynie, aby maszyna była w stanie przedstawić wynik en zewnętrznemu obserwatorowi, wówczas moglibyśmy łatwo zbudować FSM, który mógłby wytworzyć rodzaj graficzna prezentacja wyniku. Załóżmy, że FSM, po readins napisał „aaaaaabbbbbb”

000000
000000

następnie, ponieważ pręty mają tę samą długość, FSM zaakceptował ciąg „aaaaaabbbbbb”. Dwa pręty o tej samej długości oznaczają „tak”, różne długości oznaczają „nie”.

Wydaje mi się, że naginam reguły, ale tego właśnie chcę, ponieważ interesują mnie mniej lub bardziej dorozumiane założenia poczynione w dziedzinie językoznawstwa matematycznego.

FSM mogą „liczyć” w skończonym zakresie / liczbie kroków oznaczonych przez przejścia stanu. nie mogą jednak liczyć po skończonej liczbie kroków.

istnieje sens, w którym maszyna podobna do FSA może się liczyć. blisko spokrewniona maszyna nazywa się Przetwornikiem Skończonego Stanu . przetwornik może rzeczywiście liczyć w sensie „wejściowego” i wyjściowego „potoku”. pojedynczy przetwornik może pobrać sekwencję wejściową (powiedzmy w postaci binarnej) i „przekształcić” ją w sekwencję wyjściową, która jest zwiększana. następnie jeden „łączy” (identyczne) przetworniki zliczania o 1, z których każdy zwiększa swój sygnał wejściowy o 1 i wysyła go. jest również jak podstawowy „algorytm przesyłania strumieniowego” .