Quanto è pratica la teoria degli automi?

1. Hai mai usato uno strumento come grep / awk / sed? Le espressioni regolari costituiscono il cuore di questi strumenti.

2. Rimarrai sorpreso dalla quantità di codice che puoi evitare utilizzando per principio le espressioni regolari – in “progetti pratici”, come unemail server.

3. Se sei un CS major, scriverai sicuramente un compilatore / interprete per un linguaggio (almeno piccolo). Se hai mai provato questo compito prima e sei rimasto bloccato, apprezzerai quanto un po di teoria (ovvero grammatiche libere dal contesto) possa aiutarti. Questa teoria ha trasformato un compito una volta impossibile in qualcosa che può essere completato in un fine settimana. (E ha vinto linventore un premio Turing – google BNF).

4. Se sei un specialista in scienze informatiche, a un certo punto, devi sederti e pensare ai fondamenti filosofici dellinformatica, e non quanto è interessante la prossima versione dellAPI Android. In una nota correlata, è compito delluniversità non prepararti per i prossimi 5 anni della tua vita, ma prepararti per i prossimi 50. Lunica cosa che possono fare a questo riguardo è aiutarti a pensare – pensa della teoria degli automi come uno di quei corsi.

Una delle manifestazioni più pratiche di CS è Compiler Construction. Nel 1965 Knuth iniziò lo studio dei parser LR. Rapidamente (in meno di un decennio), abbiamo avuto parser LALR che sono un sottoinsieme di automi pushdown deterministici che ci consentono di implementare parser shift / reduce.

Al centro della fattibilità e dellefficienza dellanalisi LALR è una prova (di Knuth) che i “prefissi” del linguaggio risultano essere regolari (il tuo automa finito). Questa è la genesi dei generatori di parser automatizzati come yacc / bison ecc.

È sicuro dire che i linguaggi di programmazione così come li conosciamo devono gran parte della loro efficienza di compilazione a questi sviluppi.

Ecco un altro esempio: il cuore del protocollo TCP / IP è una macchina a stati finiti. Quanto più pratico può ottenere?

Ogni serio studente di informatica, specialmente quelli pratici, dovrebbe prestare attenzione alla teoria degli automi. È la base per gran parte della ricchezza dellinformatica.

Commenti

• Lanalisi dei file sorgente non è realmente la parte interessante (e importante) di un compilatore, quindi non ‘ Non credo sia corretto affermare che i ” linguaggi di programmazione così come li conosciamo devono gran parte della loro efficienza di compilazione a questi sviluppi “. Inoltre, è possibile analizzare le lingue utilizzando diversi strumenti, ad esempio PEG o analizzando i combinatori (cioè parsec).

Riesci a sentire quel rumore ? È il suono di mille brillanti teoremi, applicazioni e strumenti che ridono nel paradiso della teoria degli automi.

Le lingue e gli automi sono concetti eleganti e robusti che troverai in ogni area dellinformatica. Le lingue non sono aride, tramandate formaliste della preistoria informatica.La prospettiva della teoria del linguaggio distilla domande apparentemente complicate su oggetti sofisticati e opachi in semplici affermazioni su parole e alberi. I linguaggi formali svolgono un ruolo nellinformatica simile al punto di vista fondamentale e rivoluzionario portato dallalgebra e dalla topologia alla matematica classica. Ecco alcuni problemi pratici, abbastanza complicati, che vengono affrontati tramite la teoria del linguaggio.

1. Desideri individuare le occorrenze duplicate di una frase in un documento ed eliminare la seconda occorrenza. In sostanza, si desidera sostituire una sequenza in una lingua.
2. Un programma contiene una violazione dellasserzione? Un driver di dispositivo rispetta determinati protocolli quando interagisce con il kernel? Il comportamento di un programma è un insieme di esecuzioni; in altre parole, una lingua. La proprietà di correttezza è unaltra lingua. Il problema di correttezza del programma equivale a un controllo dellinclusione della lingua.
3. Il tuo software può essere bloccato in un ciclo infinito? Un algoritmo distribuito contiene un livelock? Abbiamo bisogno di lingue su infinite parole, ma la vista dellinclusione linguistica si applica ancora.
4. Desideri creare un disinfettante per rilevare Javascript dannoso inserito in unapplicazione web. Linsieme di stringhe dannose è un linguaggio. Linsieme di stringhe è entrato nei moduli in unaltra lingua. Vuoi determinare se lintersezione di questi linguaggi non è vuota.
5. Monitoraggio run-time di sistemi reattivi e mission-critical. Si desidera progettare un monitor software che sovrintenda al funzionamento del processo chimico o tenere traccia degli aggiornamenti a un database finanziario. Questi sono fondamentalmente problemi di inclusione e intersezione linguistica.
6. Riconoscimento di modelli con le sue numerose applicazioni. Vuoi rilevare modelli nei dati genomici, nel testo, in una serie di segnalazioni di bug. Questi sono problemi in cui ci vengono fornite parole da una lingua sconosciuta e dobbiamo indovinare la lingua. Questi sono problemi di inferenza linguistica.
7. Dato un set di documenti XML, vuoi decodificare uno schema che si applica a questi documenti. I documenti XML possono essere idealizzati come alberi. Uno schema è quindi una specifica di un linguaggio ad albero e il problema dellinferenza dello schema è un problema di inferenza del linguaggio rispetto ai linguaggi ad albero.
8. Molte applicazioni richiedono un ragionamento aritmetico automatizzato. Supponiamo di fissare una teoria logica come laritmetica di Presburger, in cui abbiamo i numeri naturali, laddizione e il predicato minore di. Una formula con n variabili rappresenta un insieme di vettori n-dimensionali. Un vettore è una sequenza di cifre e può essere codificato come una parola. Un predicato è quindi un insieme di parole; una lingua. Operazioni logiche come congiunzione, disgiunzione e negazione diventano intersezione, unione e complemento dei linguaggi (la quantificazione esistenziale è una sorta di proiezione).

La riduzione accennata sopra tratta le lingue come oggetti matematici astratti. Per applicare queste idee nella pratica, abbiamo bisogno di una struttura dati per rappresentare linguaggi e algoritmi per manipolare queste strutture dati.

Inserisci gli automi. Gli automi ci consentono di ridurre le domande sugli oggetti matematici astratti come i linguaggi a domande concrete e algoritmiche sui grafici etichettati. La teoria dei linguaggi e degli automi, oltre a un numero folle di applicazioni pratiche, fornisce un servizio intellettuale molto significativo. Possiamo pensare a problemi che vanno dalla formattazione dei codici postali alle procedure decisionali per la logica monadica del secondo ordine in uno spazio concettuale uniforme e ordinato. Quanto è sorprendente!

Non ho detto nulla sulla logica e sulle procedure decisionali. (Sì, hanno applicazioni pratiche.) Vedi la risposta di Kaveh per una panoramica autorevole.

Commenti

• haha, lironia

Come è stato spiegato nelle altre risposte, la teoria degli automi è concettualmente importante in quanto semplice modello computazionale che comprendiamo bene, e le espressioni regolari e gli automi hanno molte applicazioni nella vita reale.

Ecco “un piccolo esempio di ricerca moderna che risale alla teoria degli automi per comprendere un concetto moderno. In questo documento i ricercatori dimostrano che tutte le lingue normali hanno tester di proprietà: “Le lingue regolari sono testabili con un numero costante di query”

Non sono solo automi vanigliati. Stai “imparando le basi (accettare stati, transizioni epsilon, …) di un (computazionale) modello che aiuta a ragionare su ciò che può e, soprattutto, cosa non può essere espresso con alcuni linguaggi di query. Alcuni risultati interessanti includono:

• sì, il famoso risultato è che Gli automi finiti deterministici riconoscono le lingue normali , quindi ora lo sai di cosa hai bisogno per implementare la corrispondenza delle espressioni regolari.
• Pushdown Automata riconoscono grammatiche senza contesto : ora hai unidea di come appare un parser (o almeno una grande classe di questi).
• tree automata riconoscere le istruzioni sulla logica monadica del secondo ordine : ora hai unidea di cosa serve per implementare alcuni linguaggi di programmazione con vincoli , o … alcune istruzioni in SQL , ad esempio.

(e ovviamente sto saltando molto di altre classi)

Fondamentalmente, “è un modello molto generale. Le tue classi probabilmente enfatizzeranno il legame tra automi, linguaggi e logica.

Se stessi cercando di mettere in relazione questo con strumenti concreti “mondani”, passerei una piacevole mattinata in biblioteca a leggere un paio di parti (AB?) da Foundations of Databases di Abiteboul & al, e cercando di ricollegarlo al materiale della classe. Ovviamente è solo uno dei (molti) modi di cercare le applicazioni di una classe di automi, e credo non sia il più ovvio, ma è proprio per questo che è un esercizio interessante.

Come già sottolineato in varie risposte, la teoria degli automi nei corsi UG fornisce una struttura concettuale di base per introdurre argomenti più avanzati (e pratici) e anche per sottolineare le connessioni trascurate; per esempio: Diagrammi decisionali binari (sono DFA minimizzati; dopo aver insegnato DFA, spesso insegno a risolvere enigmi basati su BDD); scripting incluso in BioPerl e BioPython (e unottima impostazione in cui rafforzare il numero di corrispondenze indesiderate che possono essere nascoste nelle espressioni regolari di script del mondo reale), debug formale (proprietà di stato come FA negato, intersezione) e persino VCR o programmazione di allarmi intrusi domestici (ogni giorno situazione di stress di un automa scarsamente specificato insegnata attraverso esempi incompleti; forse formalizzata usando la sintesi di interfacce utente basata su scenari play-in / play-out di Harel). Uso anche limpostazione per insegnare a Python “s (quasi) puramente sottoinsieme funzionale, comprese mappe, lambda e insiemi di comprensione, utilizzando i quali si possono codificare algoritmi FA standard, spesso in un modo virtualmente indistinguibile dalle definizioni matematiche.

Commenti

• Benvenuto, Ganesh!
• Un bel modo di insegnare agli automi. Saresti disposto a condividere gli appunti delle tue lezioni?

Sono state effettuate numerose ricerche relative alla teoria degli automi nel controllo del modello utilizzato nellindustria. Dai unocchiata alle lezioni recenti di Moshe Vardi al Fields Institute , in particolare la terza lezione “Logic, Automata, Games, and Algorithms” per un assaggio del motivo per cui la teoria degli automi è ancora importante e utile.

Riassunto:

Lapproccio teorico degli automi alle procedure decisionali, introdotto da Buechi, Elgot, Rabin e Trakhtenbrot negli anni 50 e 60, è uno degli approcci più fondamentali alle procedure decisionali. Recentemente, questo approccio ha trovato applicazioni industriali nella verifica formale dei sistemi hardware e software. Il percorso dalla logica agli algoritmi pratici passa non solo attraverso gli automi, ma anche attraverso i giochi, i cui aspetti algoritmici sono stati studi di Chandra, Kozen e Stockmeyer alla fine degli anni 70. In questo discorso introduttivo descriviamo il percorso dalla logica agli algoritmi tramite automi e giochi.

Le diapositive e i file audio delle lezioni sono disponibili qui: 1 , 2 , 3 .

Getterò unaltra risposta da un angolo pratico completamente diverso: le macchine a stati finiti (o almeno alcune semplici generalizzazioni / estensioni di esse) sono spesso usate sullIA lato della programmazione del gioco. Si rivelano fornire un modello eccellente per incapsulare il comportamento dei personaggi; per esempio, un nemico potrebbe avere stati che rappresentano “pattuglia”, “ricerca”, “avvicinamento”, “attacco”, “difesa”, “ritirata”, “muori”, ecc. con transizioni ben definite tra di loro. Questo non coinvolge nessuno degli aspetti formali degli automi come i linguaggi normali e simili, ma il concetto dellautoma è molto centrale.

Abbiamo visto che il linguaggio che contrasta teoria e pratica, ponendo luna sopra laltra, è il vero compimento di ignoranza – che dimostra che un uomo non è a conoscenza dei primissimi elementi di pensiero, e va un ottimo modo per dimostrare che la sua mente è così perversa da essere incapace di ricevere loro insegnamenti.

– James Mill (scrivendo uno pseudonimo come” PQ”),” Theory and Practice “, London and Westminster Review , aprile 1836

Dovremmo prendere in considerazione la semantica delle parole “pratico” e “applicazione”. Per alcuni studenti, pratico è tutto ciò che li aiuterà a superare gli esami; per altri, tutto ciò che verrà fuori in un lavoro. In entrambi i casi, la teoria degli automi è davvero molto pratica.

Come altri sottolineano, userete le grammatiche, ad esempio, quando studiate i compilatori. Ma anche di più: comprendere lintero concetto di avere stati e regole differenti per le transizioni tra di loro può renderti un programmatore migliore quando ti rendi conto, per esempio, che il tuo codice è ridondante qua e là, e che quando lo migliori, tu stai applicando nel tuo codice le stesse idee concettuali alla base della minimizzazione di DFA.

Allo stesso modo per “applicazione”. Cosa intendi con quella parola? Anche se sei un “ingegnere con i piedi per terra” vedrai e utilizzerai idee simili a quelle della Teoria degli automi in progetti del mondo reale: codice di programmazione, diagrammi di flusso e persino il semplice ma brillante concetto di uno stack. Per i nerd della teoria come me, considero applicazioni della teoria degli automi in altre aree, come la logica, lalgebra e la teoria dei modelli finiti. Sicuramente, probabilmente non avrò mai bisogno di usare il lemma di pompaggio durante la spesa in un supermercato, ma teoremi del genere mi hanno aiutato a capire la struttura di alcune classi di linguaggi, per non parlare delle logiche e delle strutture algebriche con cui sono in corrispondenza. E questo è qualcosa che apprezzo più di qualsiasi misura di praticità.

Combinati con la logica, gli automi possono offrire modi per controlla gli stati come

$ \ qquad A \ models \ varphi $

per un automa $ A $ e una formula $ \ varphi $. Se $ A $ è un modello di sistema e $ \ varphi $ una formalizzazione delle proprietà desiderate, si ottiene la verifica del sistema, una preoccupazione molto pratica con un numero crescente di applicazioni fattibili.

Considerando il lato degli automi delle cose porta a buoni algoritmi. Ad esempio, se $ \ varphi $ è una formula LTL e $ A $ un automa Büchi (cioè un automa finito che scorre allinfinito) puoi tradurre $ \ varphi $ a un automa equivalente $ A_ \ varphi $ e controlla se $ \ cal {L} (A) \ subseteq \ cal {L} (A_ \ varphi) $

Gli automi finiti, spesso scritti come macchine a stati finiti in contesti diversi, o con le loro varianti probabilistiche, i modelli Markov nascosti possono essere applicati al riconoscimento di modelli e alla quantificazione della struttura di un modello. Per esempio. qual è il più piccolo automa finito stocastico che genererà stringhe in base, più o meno, a una data distribuzione di probabilità, o corrispondenti proprietà statistiche di un campione di stringhe (o serie temporali) da una certa distribuzione.

Vedi ad esempio CSSR , un algoritmo per la ricostruzione cieca degli stati nascosti; è più efficiente e flessibile dei modelli Markov nascosti.

Commenti

• Per aggiungere al lato pratico, i modelli Markov nascosti vengono utilizzati nel riconoscimento vocale programmi come Kurzweil.

Unaltra applicazione più pratica della teoria degli automi è lo sviluppo dellintelligenza artificiale. Lintelligenza artificiale è stata sviluppata dal concetto di automa finito. La rete neurale dei robot è costruita sulla base della teoria degli automi. Dopo che tutti i robot sono anche automi.

Alcuni hanno dato ottime risposte quando si tratta di come si relaziona allindustria. Ciò che dovrebbe essere importante è il suo valore scientifico, e la teoria degli automi è spesso la porta per comprendere prima un livello più alto di teoria del calcolo negli studi di uno studente universitario. La teoria degli automi ha una grande serie di teoremi che compaiono ovunque nellinformatica teorica, e specialmente quando si vuole parlare di applicazioni come i compilatori. Il suo valore scientifico (non è obsoleto, come potrebbe essere? È la teoria fondamentale per il campo.) È pratico per qualsiasi scienziato interessato al calcolo. È pratico in quanto è la conoscenza che è utile a coloro che capiscono o vogliono per capire la natura del calcolo. Se non riesci a trovare un uso in esso, metto in dubbio quelli che fanno ricerche o addirittura intendono studiare CS in quanto non è programmazione (questa è unapplicazione di CS), è una scienza formale.