Jak praktyczna jest teoria automatów?

Zawsze istnieje sposób na zastosowanie w tematach związanych z informatyką teoretyczną. Jednak podręczniki i kursy licencjackie zwykle nie wyjaśniają, dlaczego teoria automatów jest ważnym tematem i czy nadal ma zastosowania w praktyce. Dlatego studenci mogą mieć problemy ze zrozumieniem znaczenia teorii automatów i mogą myśleć, że nie ma ona już praktycznego zastosowania.

Czy teoria automatów jest nadal przydatna w praktyce?

Czy powinno to być częścią programu CS na studiach licencjackich?

1. Czy kiedykolwiek używałeś narzędzia takiego jak grep / awk / sed? Wyrażenia regularne stanowią serce tych narzędzi.

2. Zdziwisz się, ile kodowania możesz uniknąć, stosując wyrażenia regularne oparte na zasadach - w „praktycznych projektach”, takich jak serwer e-mail.

3. Jeśli jesteś studentem CS-dur, na pewno napiszesz kompilator / tłumacz dla (przynajmniej małego) języka. Jeśli kiedykolwiek próbowałeś tego zadania i utknąłeś, docenisz, jak mała teoria (aka gramatyka bezkontekstowa) może ci pomóc. Ta teoria sprawiła, że ​​kiedyś niemożliwe zadanie stało się czymś, co można zrealizować w ciągu weekendu. (I wygrał wynalazca nagrodę Turinga - Google BNF).

4. Jeśli jesteś studentem CS, w pewnym momencie musisz usiąść i pomyśleć o filozoficznych podstawach obliczeń, a nie tylko o tym, jak fajna jest kolejna wersja interfejsu API Androida. W związku z tym uniwersytet ma za zadanie nie przygotować cię na następne 5 lat życia, ale przygotować cię na następne 50 lat. Jedyne, co mogą zrobić w tym względzie, to pomóc ci myśleć - myśleć teorii automatów jako jeden z tych kursów.

Jednym z bardziej praktycznych przejawów CS jest budowa kompilatora. W 1965 roku Knuth rozpoczął badanie parserów LR. Szybko (w mniej niż dekadę) mieliśmy parsery LALR, które są podzbiorem deterministycznych automatów wypychających, które pozwalają nam implementować parsery shift / zmniejsz.

U podstaw wykonalności i wydajności parsowania LALR znajduje się dowód (autorstwa Knutha), że „prefiksy” języka okazują się regularne (twój skończony automat). To jest geneza automatycznych generatorów parserów, takich jak yacc / bison itp.

Można śmiało powiedzieć, że języki programowania, jakie znamy, zawdzięczają dużą część swojej wydajności kompilacji tym zmianom.

Oto inny przykład: sercem protokołu TCP / IP jest skończona maszyna stanu. O ile bardziej praktyczny może to być?

Każdy poważny student CS, szczególnie praktyczny, powinien zwrócić uwagę na teorię automatów. Jest to podstawa dużej części bogactwa informatyki.

Czy słyszysz ten hałas ? To dźwięk tysiąca genialnych twierdzeń, aplikacji i narzędzi śmiejących się w automatycznym niebie.

Języki i automaty to eleganckie i solidne pojęcia, które można znaleźć w każdej dziedzinie informatyki. Języki nie są suche, formalistyczne przekazy z prehistorii komputerowej. Perspektywa teorii języka rozdziela pozornie skomplikowane pytania o wyrafinowane, nieprzezroczyste obiekty w proste wypowiedzi na temat słów i drzew. Języki formalne odgrywają rolę w informatyce podobną do fundamentalnego i zmieniającego się punktu widzenia, który algebra i topologia wprowadziły do ​​matematyki klasycznej. Oto kilka praktycznych, dość skomplikowanych, praktycznych problemów, które można rozwiązać za pomocą teorii języka.

1. Chcesz wykryć w dokumencie zduplikowane wystąpienia frazy i usunąć drugie wystąpienie. Zasadniczo chcesz zastąpić sekwencję w języku.
2. Czy program zawiera naruszenie asercji? Czy sterownik urządzenia przestrzega określonych protokołów podczas interakcji z jądrem? Zachowanie programu jest zbiorem wykonań; innymi słowy, język. Właściwość poprawności jest innym językiem. Problem z poprawnością programu polega na sprawdzeniu włączenia języka.
3. Czy twoje oprogramowanie może utknąć w nieskończonej pętli? Czy algorytm rozproszony zawiera blokadę aktywną? Potrzebujemy języków zamiast nieskończonych słów, ale widok włączenia języka nadal obowiązuje.
4. Chcesz zbudować środek dezynfekujący do wykrywania złośliwego kodu JavaScript wprowadzonego do aplikacji internetowej. Zbiór złośliwych ciągów to język. Zestaw ciągów znaków wprowadzonych do formularzy w innym języku. Chcesz ustalić, czy przecięcie tych języków nie jest puste.
5. Monitorowanie w czasie rzeczywistym systemów reaktywnych i krytycznych dla misji. Chcesz zaprojektować monitor oprogramowania, który nadzoruje działanie twojego procesu chemicznego lub śledzić aktualizacje finansowej bazy danych. Są to problemy z włączeniem języka serca i problemami skrzyżowania.
6. Rozpoznawanie wzorów dzięki licznym zastosowaniom. Chcesz wykrywać wzorce w danych genomowych, w tekście, w serii raportów o błędach. Są to problemy, w których podajemy słowa z nieznanego języka i musimy odgadnąć ten język. Są to problemy z wnioskami językowymi.
7. Biorąc pod uwagę zestaw dokumentów XML, chcesz odtworzyć schemat, który dotyczy tych dokumentów. Dokumenty XML można idealizować jako drzewa. Schemat jest wówczas specyfikacją języka drzewiastego, a problem wnioskowania o schemat jest problemem wnioskowania językowego w stosunku do języków drzewiastych.
8. Wiele aplikacji wymaga automatycznego wnioskowania arytmetycznego. Załóżmy, że ustaliliśmy logiczną teorię, taką jak arytmetyka Presburgera, w której mamy liczby naturalne, dodawanie i mniej niż predykat. Wzór z n zmiennych reprezentuje zestaw wektorów n-wymiarowych. Wektor jest ciągiem cyfr i można go zakodować jako słowo. Predykat jest wówczas zbiorem słów; język. Operacje logiczne, takie jak koniunkcja, rozłączenie i negacja stają się przecięciem, zjednoczeniem i dopełnieniem języków (kwantyfikacja egzystencjalna jest rodzajem projekcji).

Powyższa redukcja traktuje języki jako abstrakcyjne obiekty matematyczne. Aby zastosować te pomysły w praktyce, potrzebujemy struktury danych do reprezentowania języków i algorytmów do manipulowania tymi strukturami danych.

Wprowadź automaty. Automaty pozwalają nam zredukować pytania dotyczące abstrakcyjnych obiektów matematycznych, takich jak języki, do konkretnych, algorytmicznych pytań dotyczących graficznych etykiet. Teoria języków i automatów, oprócz szalonej liczby praktycznych zastosowań, zapewnia bardzo znaczącą obsługę intelektualną. Możemy pomyśleć o problemach, od formatowania kodów pocztowych po procedury decyzyjne dla logiki monadycznego drugiego rzędu w jednolitej i uporządkowanej przestrzeni pojęciowej. Jakie to niesamowite!

Nie mówiłem nic o logice i procedurach decyzyjnych. (Tak, mają praktyczne zastosowania). Zobacz autorytatywny przegląd odpowiedzi Kaveha.

Jak wyjaśniono w innych odpowiedziach, teoria automatów jest ważna koncepcyjnie jako prosty model obliczeniowy, który dobrze rozumiemy, a wyrażenia regularne i automaty mają wiele rzeczywistych zastosowań.

Oto mały przykład współczesnych badań, które sięgają teorii automatów, aby zrozumieć nowoczesną koncepcję. W tym artykule badacze udowadniają, że wszystkie zwykłe języki mają testerów właściwości: „Zwykłe języki można testować przy stałej liczbie zapytań”

To nie tylko automaty waniliowe. Poznajesz podstawy (akceptowanie stanów, przejścia epsilon, ...) modelu (obliczeniowego), który pomaga w rozumowaniu, co może, a co ważniejsze, czego nie można wyrazić za pomocą niektórych języków zapytań. Kilka interesujących wyników to:

• tak, słynny wynik jest taki, że Deterministyczne Automaty Skończone rozpoznają języki regularne - więc teraz wiesz, czego potrzebujesz, aby wdrożyć dopasowanie wyrażeń regularnych.
• Automaty wypychające rozpoznają gramatyki bezkontekstowe - teraz masz pojęcie o tym, jak wygląda parser (lub przynajmniej duża ich klasa).
• automaty drzewa rozpoznają instrukcje na podstawie monadycznej logiki drugiego rzędu - teraz masz pojęcie, co trzeba zrobić, aby wdrożyć niektóre języki programowania z ograniczeniami lub ... na przykład niektóre instrukcje w SQL .

(i oczywiście pomijam wiele innych zajęć)

Zasadniczo jest to bardzo ogólny model. Twoje zajęcia prawdopodobnie podkreślą związek między automatami, językami i logiką.

Gdybym zastanawiał się nad powiązaniem tego z konkretnymi „światowymi” narzędziami, spędziłbym wolny czas w bibliotece, czytając kilka części (AB?) Z Fundacji baz danych autorstwa Abiteboul i in. I próbując połączyć to z powrotem z materiałem klasowym . Oczywiście jest to tylko jeden z (wielu) sposobów poszukiwania aplikacji klasy automatów, i chyba nie jest to najbardziej oczywiste - ale właśnie dlatego jest to interesujące ćwiczenie.

Jak już wskazano w różnych odpowiedziach, teoria automatów na kursach UG stanowi jedną z podstawowych ram koncepcyjnych do wprowadzania bardziej zaawansowanych (i praktycznych) tematów, a także do wskazywania pomijanych połączeń; na przykład: Diagramy decyzyjne binarne (są zminimalizowane DFA; po nauczeniu DFA często uczę rozwiązywania zagadek opartych na BDD); skrypty, w tym w BioPerl i BioPython (i świetne ustawienie, w którym można wzmocnić liczbę niezamierzonych dopasowań, które mogą być ukryte w regexps skryptu w świecie rzeczywistym), formalne debugowanie (właściwości stanu jako zanegowane FA, przecinają się), a nawet programowanie VCR lub alarmów domowych intruzów (codzienna sytuacja stresowa słabo określonego automatu nauczana na niekompletnych przykładach; być może sformalizowana przy użyciu opartej na scenariuszach syntezy interfejsów użytkownika Harel). Korzystam również z tego ustawienia, aby uczyć Pythona

Wyrzucę inną odpowiedź z zupełnie innej praktycznej strony: maszyny stanów skończonych (lub przynajmniej niektóre ich proste uogólnienia / rozszerzenia) są często używane po stronie AI programowania. Okazały się doskonałym modelem do enkapsulacji zachowania postaci; na przykład wróg może mieć stany reprezentujące „patrol”, „poszukiwanie”, „podejście”, „atak”, „obronę”, „odwrót”, „śmierć” itp., z dobrze zdefiniowanymi przejściami między nimi. Nie obejmuje to żadnego z formalnych aspektów automatów, takich jak zwykłe języki i tym podobne, ale koncepcja automatu jest bardzo podstawowa.

Widzieliśmy, że język przeciwstawiający się teorii i praktyce, stawiający jeden nad drugim, jest właśnie szczytem ignorancji - dowodzi, że człowiek nie jest zaznajomiony z pierwszymi elementami myśli, i jest świetną drogą do udowodnienia swojego umysł jest tak wypaczony, że nie jest w stanie ich nauczyć.

- James Mill (pseudonim „PQ”), „Teoria i praktyka”, Londyn i Westminster Review , kwiecień 1836

Przeprowadzono wiele badań związanych z teorią automatów w sprawdzaniu modeli stosowanych w przemyśle. Sprawdź ostatnie wykłady Moshe Vardi w Fields Institute , w szczególności trzeci wykład „Logika, automaty, gry i algorytmy”, aby dowiedzieć się, dlaczego teoria automatów jest nadal ważna i przydatna.

Abstrakcyjny:

Automatyzowane teoretycznie podejście do procedur decyzyjnych, wprowadzone przez Buechi, Elgot, Rabina i Trakhtenbrota w latach 50. i 60. XX wieku, jest jednym z najbardziej podstawowych podejść do procedur decyzyjnych. Niedawno takie podejście znalazło zastosowania przemysłowe w formalnej weryfikacji sprzętu i oprogramowania. Ścieżka od logiki do praktycznych algorytmów prowadzi nie tylko przez automaty, ale także przez gry, których aspektami algorytmicznymi były badania Chandry, Kozen i Stockmeyera pod koniec lat siedemdziesiątych. W tym omówieniu omówimy ścieżkę od logiki do algorytmów za pośrednictwem automatów i gier.

Slajdy i pliki audio z wykładów są dostępne tutaj: 1 , 2 , 3 .

Powinniśmy wziąć pod uwagę semantykę słów „praktyczny” i „zastosowanie”. Dla niektórych studentów praktyczne jest wszystko, co pomoże im zdać egzamin; dla innych wszystko, co pojawi się w pracy. W obu przypadkach teoria automatów jest rzeczywiście bardzo praktyczna.

Jak podkreślają inni, będziesz używać gramatyki, na przykład, podczas nauki kompilatorów. Ale nawet więcej: zrozumienie całej koncepcji posiadania różnych stanów i reguł przejścia między nimi może uczynić cię lepszym programistą, gdy zdasz sobie sprawę, na przykład, że twój kod jest tu i tam zbędny, a kiedy go poprawisz, będziesz są stosowania w kodzie same konceptualnych idei tył minimalizacji DFA.

Podobnie w przypadku „aplikacji”. Co rozumiesz przez to słowo? Nawet jeśli jesteś „przyziemnym inżynierem”, zobaczysz i zastosujesz pomysły podobne do teorii Automaty w rzeczywistych projektach: kodowanie kodu, diagramy przepływu, a nawet prosta, ale genialna koncepcja stosu. W przypadku takich frajerów teorii jak ja rozważam zastosowanie teorii automatów w innych obszarach, takich jak logika, algebra i teoria modeli skończonych. Z pewnością prawdopodobnie nigdy nie będę musiał używać lematu pompującego podczas zakupów w supermarkecie, ale takie twierdzenia pomogły mi zrozumieć strukturę niektórych klas języków, nie wspominając już o logice i strukturach algebraicznych, z którymi się korespondują. I to jest coś, co cenię bardziej niż jakakolwiek praktyczność.

Rzucone razem z logiką automaty mogą oferować sposoby sprawdzania statystyk takich jak

$\qquad A \models \varphi$

$A$$\varphi$$A$$\varphi$

$\varphi$$A$$\varphi$$A_\varphi$$\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Automaty skończone, często opisywane jako maszyny skończone w różnych kontekstach lub z ich wariantami probabilistycznymi Ukryte modele Markowa mogą być stosowane do rozpoznawania wzorów i kwantyfikacji struktury wzoru. Na przykład, jakie są najmniejsze stochastyczne automaty skończone, które będą generować łańcuchy mniej więcej zgodnie z danym rozkładem prawdopodobieństwa lub dopasowanie właściwości statystycznych próbki łańcuchów (lub szeregów czasowych) z pewnego rozkładu.

Zobacz na przykład CSSR , algorytm ślepej rekonstrukcji stanów ukrytych; jest bardziej wydajny i elastyczny niż ukryte modele Markowa.

Kolejnym bardziej praktycznym zastosowaniem teorii automatów jest rozwój sztucznej inteligencji. Sztuczna inteligencja została opracowana na podstawie koncepcji automatu skończonego. Sieć neuronowa robotów jest budowana na podstawie teorii automatów. W końcu wszystkie roboty są również automatami.

Niektórzy dali świetne odpowiedzi, jeśli chodzi o związek z przemysłem. Co powinno być ważne, to jego wartość naukowa, a teoria automatów jest często bramą do zrozumienia wyższego poziomu teorii obliczeń w studiach licencjackich. Teoria automatów ma wielki zestaw twierdzeń, które pojawiają się wszędzie w Teoretycznej Informatyce, a zwłaszcza gdy chce się mówić o aplikacjach takich jak Kompilatory. Jego wartość naukowa (jak nie jest przestarzała, jak może być? To podstawowa teoria w tej dziedzinie.) Jest praktyczna dla każdego naukowca, który jest zainteresowany obliczeniami. Jest to praktyczne, ponieważ wiedza jest przydatna dla tych, którzy rozumieją lub chcą zrozumieć naturę obliczeń. Jeśli nie możesz znaleźć w nim zastosowania, kwestionuję badania, a nawet zamiar studiowania CS, ponieważ to nie jest programowanie (że „