Jak praktyczna jest teoria automatów?

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

2. Zdziwisz się, jak bardzo możesz uniknąć kodowania dzięki zasadowemu stosowaniu wyrażeń regularnych – w „praktycznych projektach”, takich jak e-mail serwer.

3. Jeśli jesteś głównym specjalistą ds. informatyki, na pewno będziesz pisać kompilator / interpreter dla (przynajmniej małego) języka. Jeśli kiedykolwiek próbowałeś to zadanie przed i utknęło w miejscu, z pewnością docenisz, jak bardzo mała teoria (zwana również gramatyką bezkontekstową) może ci pomóc. Ta teoria przekształciła niegdyś niemożliwe zadanie w coś, co można ukończyć w weekend. (I wygrał wynalazca nagroda Turinga – Google BNF).

4. Jeśli jesteś magistrem informatyki, w pewnym momencie musisz usiąść i pomyśleć o filozoficznych podstawach informatyki, a nie tylko o tym, jak fajna jest następna wersja interfejsu API systemu Android. A propos, zadaniem uniwersytetu nie jest przygotowanie cię na następne 5 lat twojego życia, ale przygotowanie cię na następne 50. Jedyne, co mogą zrobić w tym zakresie, to pomóc ci myśleć – myśleć teorii automatów jako jednego z tych kursów.

Jeden z bardziej praktycznych przejawów CS to konstrukcja kompilatora. W 1965 roku Knuth rozpoczął badanie parserów LR. Szybko (w mniej niż dekadę) otrzymaliśmy parsery LALR, które są podzbiorem deterministycznych automatów przesuwających w dół, które pozwalają nam zaimplementować parsery przesunięcia / zmniejszenia.

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

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

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

Każdy poważny student CS, zwłaszcza praktyczny, powinien zwrócić uwagę na teorię automatów. Stanowi podstawę wielu bogactw informatyki.

Komentarze

• Parsowanie plików źródłowych nie jest tak naprawdę interesującą (i ważną) częścią kompilatora, więc nie ' nie sądzę, że można bezpiecznie powiedzieć, że ” języki programowania, jakie znamy, zawdzięczają znaczną część wydajności kompilacji tym zmianom „. Ponadto możliwe jest analizowanie języków przy użyciu różnych narzędzi, na przykład PEG-ów lub kombinacji parsujących (np. Parsek).

Czy słyszysz ten hałas ? To dźwięk tysięcy genialnych twierdzeń, zastosowań i narzędzi śmiejących się w niebie teorii automatów.

Języki i automaty to eleganckie i solidne koncepcje, które można znaleźć w każdej dziedzinie informatyki. Języki nie są suche, formalistyczne przejawy prehistorii komputerów.Perspektywa teorii języka destyluje pozornie skomplikowane pytania dotyczące wyrafinowanych, nieprzejrzystych przedmiotów w proste stwierdzenia dotyczące słów i drzew. Języki formalne odgrywają w informatyce rolę podobną do podstawowego i zmieniającego grę punktu widzenia, wniesionego przez algebrę i topologię do klasycznej matematyki. Oto kilka praktycznych, dość skomplikowanych, praktycznych problemów, do których można podejść poprzez teorię języka.

1. Chcesz znaleźć zduplikowane wystąpienia frazy w dokumencie 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 to zestaw wykonań; innymi słowy, język. Właściwość poprawności to inny język. Problem z poprawnością programu sprowadza się do sprawdzenia włączenia języka.
3. Czy oprogramowanie może utknąć w nieskończonej pętli? Czy rozproszony algorytm zawiera livelock? 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 znaków to język. Zestaw ciągów wpisanych do formularzy w innym języku. Chcesz określić, czy przecięcie tych języków nie jest puste.
5. Monitorowanie w czasie wykonywania systemów reaktywnych i krytycznych dla misji. Chcesz zaprojektować oprogramowanie monitorujące, które nadzoruje przebieg procesu chemicznego lub śledzi aktualizacje finansowej bazy danych. Są to problemy związane z włączaniem i przecinaniem języka.
6. Rozpoznawanie wzorców z jego licznymi zastosowaniami. Chcesz wykryć wzorce w danych genomowych, w tekście, w serii raportów o błędach. Są to problemy, w których otrzymujemy słowa z nieznanego języka i musimy odgadnąć język. To są problemy z wnioskiem językowym.
7. Biorąc pod uwagę zestaw dokumentów XML, chcesz odtworzyć schemat, który ma zastosowanie do tych dokumentów. Dokumenty XML można wyidealizować jako drzewa. Schemat jest zatem specyfikacją języka drzewa, a problem wnioskowania o schemacie jest problemem wnioskowania językowego w odniesieniu do języków drzewa.
8. Wiele aplikacji wymaga automatycznego rozumowania arytmetycznego. Załóżmy, że naprawimy teorię logiczną, taką jak arytmetyka Presburgera, w której mamy liczby naturalne, dodawanie i predykat mniej niż. Formuła zawierająca n zmiennych reprezentuje zbiór n-wymiarowych wektorów. Wektor jest sekwencją cyfr i może być zakodowany jako słowo. Predykat jest więc zbiorem słów; język. Operacje logiczne, takie jak koniunkcja, dysjunkcja i negacja, stają się przecięciem, zjednoczeniem i dopełnieniem języków (kwantyfikacja egzystencjalna jest rodzajem projekcji).

Wspomniana powyżej 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 oznaczonych wykresów. Języki i teoria automatów, oprócz szalonej liczby praktycznych zastosowań, dostarczają bardzo znaczących usług intelektualnych. Możemy myśleć o problemach, od formatowania kodów pocztowych po procedury decyzyjne dla monadycznej logiki drugiego rzędu w jednolitej i uporządkowanej przestrzeni koncepcyjnej. Jakie to niesamowite!

Nic nie mówiłem o logice i procedurach decyzyjnych. (Tak, mają praktyczne zastosowania). Zobacz odpowiedź Kaveha, aby uzyskać miarodajny przegląd.

Komentarze

• haha, ironia

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ą do teorii automatów, aby zrozumieć współczesną koncepcję. W tym artykule naukowcy udowodnili, że wszystkie języki zwykłe mają testery właściwości: „Języki regularne można testować przy użyciu stałej liczby zapytań”

To nie tylko zwykłe automaty. Uczysz się podstaw (akceptowanie stanów, przejść epsilon, …) a (obliczeniowego) model, który pomaga w rozumowaniu, co można, a co ważniejsze, czego nie można wyrazić w niektórych językach zapytań. Oto kilka interesujących wyników:

• tak, słynny wynik jest taki, że Deterministyczne automaty skończone rozpoznają języki regularne – teraz już wiesz czego potrzebujesz, aby zaimplementować dopasowywanie wyrażeń regularnych.
• Automaty przesuwające w dół rozpoznają gramatyki bezkontekstowe – teraz masz wyobrażenie o tym, jak wygląda parser (lub przynajmniej duża ich klasa).
• drzewa automaty rozpoznawać instrukcje w monadycznej logice drugiego rzędu – teraz masz pojęcie, czego potrzeba, aby zaimplementować niektóre języki programowania z ograniczeniami , lub … na przykład niektóre instrukcje SQL .

(i oczywiście bardzo pomijam innych klas)

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

Gdybym szukał odniesienia do konkretnych „światowych” narzędzi, spędziłbym spokojny poranek w bibliotece, czytając kilka fragmentów (AB?) z Foundations of Databases autorstwa Abiteboul & al i próbuję połączyć to z powrotem z materiałami klasowymi. Oczywiście to tylko jeden z (wielu) sposobów wyszukiwania aplikacji klasy automatów i nie wydaje mi się, aby był to najbardziej oczywisty – ale właśnie dlatego jest to interesujące ćwiczenie.

Jak już wskazano w różnych odpowiedziach, teoria automatów w kursach UG stanowi podstawowe ramy koncepcyjne do wprowadzenia bardziej zaawansowanych (i praktycznych) tematów, a także za wskazywanie przeoczonych połączeń; na przykład: binarne diagramy decyzyjne (są to zminimalizowane DFA; po nauczaniu DFA często uczę rozwiązywania zagadek w oparciu o BDD); skrypty, w tym w BioPerl i BioPython (i świetne ustawienie, w którym można wzmocnić, ile niezamierzonych dopasowań może być ukrytych w rzeczywistych wyrażeniach regularnych skryptu), formalne debugowanie (właściwości stanu jako zanegowane FA, przecięcie), a nawet programowanie VCR lub domowego alarmu włamaniowego (codzienna sytuacja stresowa źle sprecyzowanego automatu nauczana na niekompletnych przykładach; być może sformalizowana za pomocą syntezy interfejsów użytkownika opartej na scenariuszu play-in / play-out Harela). podzbiór funkcjonalny, w tym mapy, wyrażenia lambda i zestawy wyrażeń, za pomocą których można zakodować standardowe algorytmy FA, często w sposób praktycznie nie do odróżnienia od wartości matematycznych.

Komentarze

• Witaj, Ganesh!
• Fajny sposób na nauczanie automatów. Czy zechciałbyś podzielić się notatkami z wykładów?

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żne i użyteczne.

Streszczenie:

Teoretyczne podejście do procedur decyzyjnych oparte na teorii automatów, wprowadzone przez Buechi, Elgot, Rabin i Trakhtenbrot w latach 50. i 60. to jedno z najbardziej fundamentalnych podejść do procedur decyzyjnych. Ostatnio podejście to znalazło przemysłowe zastosowanie w formalnej weryfikacji systemów sprzętowych i programowych. Droga od logiki do praktycznych algorytmów prowadzi nie tylko przez automaty, ale także poprzez gry, których aspekty algorytmiczne były badane przez Chandrę, Kozen i Stockmeyer pod koniec lat 70. W tym omówieniu omówimy ścieżkę od logiki do algorytmów za pomocą automatów i gier.

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

Wyrzucę inną odpowiedź z zupełnie innego praktycznego punktu widzenia: maszyny o skończonych stanach (lub przynajmniej niektóre ich proste uogólnienia / rozszerzenia) są często używane w sztucznej inteligencji strona programowania gier. Okazało się, że stanowią doskonały model hermetyzacji zachowania postaci; na przykład wróg może mieć stany reprezentujące „patrol”, „poszukiwanie”, „podejście”, „atak”, „obrona”, „odwrót”, „śmierć” itp. z dobrze zdefiniowanymi przejściami między nimi. Nie obejmuje to żadnych 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, który przeciwstawia teorię i praktykę, stawia jedne ponad drugimi, jest doskonałym ignorancji – że udowadnia, że człowiek nie jest zaznajomiony z pierwszymi elementami myśli i stanowi świetny sposób na udowodnienie, że jego umysł jest tak zboczony, że nie można go ich nauczyć.

– James Mill (piszący pseudonimem jako„ PQ”),„ Theory and Practice ”, London and Westminster Review , kwiecień 1836

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

Jak inni zwracają uwagę, 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ł dla przejść między nimi może uczynić z Ciebie lepszego programistę, gdy zdasz sobie na przykład sprawę, że Twój kod jest tu i ówdzie zbędny, a kiedy go poprawisz, stosują w swoim kodzie te same pomysły koncepcyjne za minimalizacją DFA.

Podobnie dla „aplikacji”. Co rozumiesz przez to słowo? Nawet jeśli jesteś „przyziemnym inżynierem”, zobaczysz i wykorzystasz pomysły podobne do tych z teorii automatów w rzeczywistych projektach: kod programowania, diagramy przepływu, a nawet prosta, ale genialna koncepcja stosu. Dla miłośników teorii takich jak ja rozważam zastosowania teorii automatów w innych dziedzinach, takich jak logika, algebra i teoria modeli skończonych. Z pewnością prawdopodobnie nigdy nie będę musiał używać lematu o pompowaniu podczas zakupów w supermarkecie, ale takie twierdzenia pomogły mi zrozumieć strukturę niektórych klas języków, nie wspominając o logikach i strukturach algebraicznych, z którymi są one powiązane. I to jest coś, co cenię bardziej niż jakakolwiek miara praktyczności.

W połączeniu z logiką automaty oferują sposoby sprawdź statystyki takie jak

$ \ qquad A \ models \ varphi $

dla automatu $ A $ i wzoru $ \ varphi $. Jeśli $ A $ jest modelem systemu, a $ \ varphi $ formalizacją pożądanych właściwości, otrzymujesz weryfikację systemu, bardzo praktyczny problem z rosnącą liczbą wykonalnych aplikacji.

Biorąc pod uwagę stronę automatów prowadzi do ładnych algorytmów. Na przykład, jeśli $ \ varphi $ jest formułą LTL , a $ A $ automatem Büchi (tj. Nieskończenie działającym automatem skończonym), możesz przetłumaczyć $ \ varphi $ do równoważnego automatu $ A_ \ varphi $ i sprawdź, czy $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Automaty skończone, często opisywane jako automaty skończone w różnych kontekstach lub z ich probabilistycznymi wariantami Ukryte modele Markowa można zastosować do rozpoznawania wzorców i kwantyfikacji struktury wzorca. Na przykład. jakie są najmniejsze stochastyczne automaty skończone, które będą generować ciągi zgodnie z, mniej więcej, danym rozkładem prawdopodobieństwa lub dopasowaniem właściwości statystycznych próbki ciągów (lub szeregów czasowych) z jakiegoś rozkładu.

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

Komentarze

• Aby dodać coś praktycznego, w rozpoznawaniu mowy używane są ukryte modele Markowa programy takie jak Kurzweil.

Innym, bardziej praktycznym zastosowaniem teorii automatów jest rozwój sztucznej inteligencji. Sztuczna inteligencja została opracowana z koncepcji automatu skończonego. Sieć neuronowa robotów jest zbudowana w oparciu o teorię automatów. Przecież roboty są także automatami.

Niektórzy udzielili świetnych odpowiedzi, jeśli chodzi o ich związek z przemysłem. Ważna powinna być jej wartość naukowa, a teoria automatów jest często bramą do zrozumienia wyższego poziomu teorii obliczeń na studiach licencjackich. Teoria automatów ma wielki zestaw twierdzeń, które pojawiają się wszędzie w informatyce teoretycznej, a zwłaszcza gdy chce się mówić o zastosowaniach, takich jak kompilatory. Jej wartość naukowa (nie jest przestarzała, jak to możliwe? To podstawowa teoria w tej dziedzinie.) Jest praktyczna dla każdego naukowca zainteresowanego obliczeniami. Jest praktyczna, ponieważ jest to wiedza przydatna dla tych, którzy rozumieją lub chcą aby zrozumieć naturę obliczeń. Jeśli nie możesz znaleźć w nich zastosowania, kwestionuję badania lub nawet zamierzam studiować CS, ponieważ to nie jest programowanie (to jest aplikacja CS), to nauka formalna.