Indietro

ⓘ Categoria:Teoria dei linguaggi formali




                                               

Automa a stati finiti deterministico

Nella teoria del calcolo, un automa a stati finiti deterministico o deterministic finite automaton è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso cè una ed una sola transizione allo stato successivo.

                                               

Automa a stati finiti non deterministico

Nella teoria del calcolo, un automa a stati finiti non deterministico è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione. Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.

                                               

Automa lineare limitato

Un automa lineare limitato è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dellinput. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto. Come una macchina di Turing, il nastro di un LBA è composto da celle che possono contenere simboli appartenenti ad un alfabeto finito. Lautoma possiede un numero finito di stati e la sua testina può leggere e scrivere una sola cella per volta.

                                               

Backus-Naur Form

La BNF è una metasintassi, ovvero un formalismo attraverso cui è possibile descrivere la sintassi di linguaggi formali. Si tratta di uno strumento molto usato per descrivere in modo preciso e non ambiguo la sintassi dei linguaggi di programmazione, dei protocolli di rete e così via, benché non manchino in letteratura esempi di sue applicazioni a contesti anche non informatici e addirittura non tecnologici. La BNF viene usata nella maggior parte dei testi sulla teoria dei linguaggi di programmazione e in molti testi introduttivi su specifici linguaggi. In termini formali, la BNF può essere ...

                                               

Chiusura induttiva

Sia A {\displaystyle {\mathcal {A}}} un insieme e F {\displaystyle {\mathcal {F}}} un insieme di operazioni di arietà assegnata. Si definisce chiusura induttiva C l o s A, F {\displaystyle {\mathcal {C}}los\left{\mathcal {A}},{\mathcal {F}}\right} il minimo insieme che verifica le seguenti condizioni: Se {\displaystyle \leftx_{1},x_{2}.,x_{n}\right} sono elementi di C l o s A, F {\displaystyle {\mathcal {C}}los\left{\mathcal {A}},{\mathcal {F}}\right}, f ∈ F {\displaystyle f\in {\mathcal {F}}} e f {\displaystyle f\leftx_{1},x_{2}.,x_{n}\right} è definita in F {\displaystyle {\mathcal {F}}} ...

                                               

Compilatore

Un compilatore è un programma informatico che traduce una serie di istruzioni scritte in un determinato linguaggio di programmazione in istruzioni di un altro linguaggio. Il processo di traduzione si chiama compilazione mentre lattività inversa - ovvero passare dal codice oggetto al codice sorgente - è chiamata decompilazione ed è effettuata per mezzo di un decompilatore. Se tutti i compilatori aderissero esattamente alla specifica del linguaggio, lo stesso programma potrebbe essere compilato senza modifiche da ciascun compilatore, producendo risultati semanticamente uguali, ovvero program ...

                                               

Costruzione dei sottoinsiemi

Nella teoria dei linguaggi formali, la costruzione dei sottoinsiemi o subset construction è la tecnica di costruzione dellautoma a stati finiti deterministico equivalente ad un automa a stati finiti non deterministico.

                                               

EBNF

La EBNF è una delle varianti più conosciute della BNF. Essa è la sua forma estesa. La EBNF è definita come standard internazionale da ISO-14977, ma ad esempio il W3C utilizza una EBNF differente per definire la sintassi XML: sebbene le espansioni rispetto alla BNF siano più o meno le stesse, i caratteri utilizzati per individuarle non sono universalmente condivisi.

                                               

Errore di sintassi

In informatica un errore di sintassi è un errore di programmazione che può essere presente allinterno di un file di codice, causato solitamente dal ricorso a una sintassi errata o comunque non contemplata dal linguaggio di programmazione in uso. I linguaggi di programmazione e di specifica prevedono infatti che le istruzioni e gli eventuali blocchi funzionali siano inseriti seguendo una serie di regole formali, tipiche e proprie di ogni linguaggio, che stabiliscano come queste istruzioni vengano correttamente lette/interpretate dalla macchina. Le regole formali permettono quindi di individ ...

                                               

Esponente critico

In dinamica simbolica, l esponente critico di una successione infinita di simboli è una quantità che descrive quante volte una stringa può ripetersi allinterno della sequenza.