In matematica , informatica e linguistica , un linguaggio formale è un insieme di parole . L'alfabeto di una lingua formale è l'insieme di simboli, lettere o lessemi che servono per costruire le parole della lingua; spesso si presume che questo alfabeto sia finito. Lo scopo della teoria del linguaggio formale è descrivere i linguaggi formali.
Le parole sono sequenze di elementi di questo alfabeto; le parole che appartengono a un particolare linguaggio formale sono talvolta chiamate parole ben formate o formule ben formate . Un linguaggio formale è spesso definito da una grammatica formale , come le grammatiche algebriche, e analizzato da automi .
La teoria dei linguaggi formali studia gli aspetti puramente sintattici di tali linguaggi, vale a dire la loro struttura interna formale. La teoria del linguaggio deriva dalla linguistica , come mezzo per comprendere le regolarità sintattiche delle lingue naturali :
Lo studio dei linguaggi formali comprende tutti i mezzi di descrizione e analisi di questi linguaggi, come le grammatiche formali per la generazione e gli automi per il riconoscimento, ma si interessa anche all'apprendimento automatico e alla traduzione linguaggi automatici . Nel campo della traduzione, la teoria del linguaggio si applica ai compilatori di linguaggi di programmazione.
Ci diamo un insieme , chiamato alfabeto i cui elementi sono chiamati lettere .
Questa legge di composizione interna è associativa e ammette la parola vuota per elemento neutro (che giustifica la notazione ). Di conseguenza l'insieme , provvisto di questa legge, è un monoide . È un monoide libero nel senso dell'algebra.
Un linguaggio formale è un insieme di parole su un alfabeto finito, vale a dire una parte del monoide libero su questo alfabeto.
Alcuni esempi di linguaggi formali:
Un linguaggio formale può essere specificato con mezzi diversi. Ciò che si cerca è un metodo o meccanismo finito ed esplicito che permetta di produrre o analizzare un linguaggio generalmente infinito. Tra questi metodi ci sono:
Le domande tipiche che ci poniamo su un linguaggio formale sono le seguenti:
Queste domande hanno collegamenti con la computabilità e la teoria della complessità .
Le lingue sono raggruppate in famiglie linguistiche. La Gerarchia Chomsky ci fornisce quattro tipi di grammatica, ogni tipo di grammatica genera una famiglia linguistica.
Questi insiemi di lingue sono tutti inclusi l'uno nell'altro e sono qui indicati dal più grande al più piccolo. Quindi tutto il linguaggio razionale è algebrico , che è esso stesso contestuale , che è esso stesso ricorsivamente enumerabile .
Tra queste 4 famiglie di lingue si possono notare famiglie che non fanno parte della gerarchia di Chomsky, ma che rimangono notevoli per le loro definizioni e le loro proprietà. I linguaggi deterministici context-free sono i linguaggi riconosciuti dagli automi deterministic stack , e sono strettamente inclusi nella famiglia dei linguaggi algebrici. Le lingue ricorsive sono le lingue riconosciute da una macchina di Turing, e il cui complemento è riconosciuto anche da una macchina di Turing. Sono quindi strettamente inclusi nei linguaggi ricorsivamente enumerabili .
Diverse operazioni possono essere utilizzate per creare nuove lingue da determinate lingue. Supponiamo che L e M siano lingue su un alfabeto comune.
Le operazioni di intersezione , unione e complementazione degli insiemi sono definite come per qualsiasi insieme.
La concatenazione di L e M , appena notata è l'insieme delle parole della forma xy , dove x è una parola di L e c'è una parola di M .
Il quoziente a sinistra di una parola è l'insieme di parole come appartiene a . Il quoziente a sinistra è anche chiamato residuo .
Il quoziente a destra di una parola è definito simmetricamente come l'insieme di parole come appartiene a .
Il quoziente a sinistra e il quoziente a destra si estendono alle lingue. Quindi, il quoziente a sinistra di una lingua , indicato , è l'unione delle lingue per in .
La stella Kleene di L è il set notato composto da parole della forma con e . Questo set contiene la parola vuoto .
Il rovescio di L , annotato o contiene le parole speculari delle parole di L , vale a dire le parole di L lette da destra a sinistra.
La miscela di L e M , denotata L Ш M è l'insieme di parole che possono essere scritte dove e sono parole (possibilmente vuote) come una parola di L e una parola da M . Per esempio Ш .
Un'applicazione è un morfismo o un omomorfismo se per tutte le parole di . L'immagine omomorfa di una lingua su è l'insieme
.Abusando del linguaggio, chiamiamo morfismo inverso l'inverso di un morfismo. Il morfismo inverso di è la funzione denotata di nell'insieme delle parti di definito da
.In genere non è un morfismo. L'immagine da un morfismo inverso di una lingua su è la lingua
.Un morfismo è non cancellante o crescente o, per imitazione dell'inglese, privo di se l'immagine di una lettera non è mai la parola vuota. In questo caso, la lunghezza dell'immagine di una parola è maggiore o uguale a quella della parola.
Una domanda comune su queste operazioni è conoscere le proprietà di chiusura di ciascuna famiglia linguistica per ciascuna di queste operazioni, ovvero se la lingua risultante da un'operazione rimane nella stessa famiglia di lingue delle lingue da cui proviene.
Lingue razionali Ra |
Linguaggi algebrici deterministici |
Linguaggi algebrici |
Lingue contestuali |
linguaggi ricorsivi |
Linguaggi ricorsivamente enumerabili |
|
---|---|---|---|---|---|---|
Unione | Chiuso | Nessun recinto | Chiuso | Chiuso | Chiuso | Chiuso |
Intersezione | Chiuso | Nessun recinto | Nessun recinto | Chiuso | Chiuso | Chiuso |
Complementare | Chiuso | Chiuso | Nessun recinto | Chiuso | Chiuso | Nessun recinto |
Concatenazione | Chiuso | Nessun recinto | Chiuso | Chiuso | Chiuso | Chiuso |
Stella di Kleene | Chiuso | Nessun recinto | Chiuso | Chiuso | Chiuso | Chiuso |
Specchio | Chiuso | Nessun recinto | Chiuso | Chiuso | Chiuso | Chiuso |
Misto | Chiuso | Nessun recinto | Nessun recinto | Nessun recinto | Nessun recinto | Nessun recinto |
Morfismo | Chiuso | Nessun recinto | Chiuso | Nessun recinto | Nessun recinto | Chiuso |
Morfismo in crescita | Chiuso | Nessun recinto | Chiuso | Chiuso | Chiuso | Chiuso |
Morfismo inverso | Chiuso | Chiuso | Chiuso | Chiuso | Chiuso | Chiuso |