Storie di una vita mera(vigliosa)
Dove Sono: vicino a te.
Come Sono: sarò bre
1.09.2007 2:31 PM
Linguaggi inerentemente ambigui
"In matematica, logica, informatica e linguistica, per linguaggio formale si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.
Di un linguaggio formale può far parte o meno la stringa muta o parola vuota, cioè la sequenza costituita da zero caratteri: questa spesso viene denotata come e, ε o λ: qui preferiamo usare μ.
Un linguaggio può essere finito o infinito in quanto non si pongono limiti alla lunghezza delle stringhe.
Un tipico alfabeto potrebbe essere A := {a, b} e tipiche stringhe su questo alfabeto
ababba aaabbbaaa aaabbbabaababb .
Esempi di linguaggi formali su A sono:
* il linguaggio di tutte le stringhe che contengono lo stesso numero di a e di b;
* lo stesso insieme di tutte le parole su A e lo stesso insieme vuoto;
* l'insieme delle stringhe della forma an con n numero primo;
* l'insieme dei programmi in un dato linguaggio di programmazione che si dimostrano sintatticamente corretti;
* l'insieme delle stringhe che, immesse in una macchina di Turing, la fanno evolvere fino ad un arresto.
Un linguaggio formale può essere definito in una grande varietà di modi.
* come insieme delle stringhe derivate nell'ambito di una grammatica formale (v. gerarchia di Chomsky);
* stringhe fornite da un'espressione regolare;
* stringhe accettate da qualche automa, come una macchina di Turing o un automa a stati finiti;
* nell'ambito di un insieme di domande la cui risposta può essere solo SI o NO, le domande a risposta affermativa (v. problema di decisione).
I linguaggi si possono comporre con molte operazioni e in tal modo si possono ottenere molti linguaggi a partire da un insieme di linguaggi dati. Con L1 ed L2 denotiamo due linguaggi sopra un dato alfabeto.
* La concatenazione o giustapposizione L1L2 consiste di tutte le stringhe della forma vw dove v è una stringa di L1 e w una stringa di L2.
* L' intersezione di L1 ed L2 consiste di tutte le stringhe contenute sia in L1 che in L2.
* L' unione di L1 ed L2 consiste di tutte le stringhe che sono contenute in L1 o in L2.
* Il complemento del linguaggio L1 consiste di tutte le stringhe sopra l'alfabeto che non sono contenute in L1.
* Il quoziente destro L1/L2 di L1 da L2 consiste di tutte le stringhe v per le quali esiste una stringa w in L2 tale che vw si trova in L1.
* La star di Kleene L1* consiste di tutte le stringhe che possono essere scritte nella forma w1w2...wn con le stringhe wi in L1 ed n ≥ 0. Si noti che questo include la stringa muta in quanto si ammette n = 0.
* Il riflesso L1R contiene le stringhe riflesse, capovolte, di tutte le stringhe in L1.
* Il mescolamento o shuffle di L1 ed L2 consiste di tutte le stringhe che si possono scrivere nella forma v1w1v2w2...vnwn, dove n ≥ 1 and v1,...,vn sono stringhe tali che la concatenazione v1...vn si trova in L1 e w1,...,wn sono stringhe tali che w1...wn si trova L2."
Ovvio, no? No. Per un bel cazzo.
Di un linguaggio formale può far parte o meno la stringa muta o parola vuota, cioè la sequenza costituita da zero caratteri: questa spesso viene denotata come e, ε o λ: qui preferiamo usare μ.
Un linguaggio può essere finito o infinito in quanto non si pongono limiti alla lunghezza delle stringhe.
Un tipico alfabeto potrebbe essere A := {a, b} e tipiche stringhe su questo alfabeto
ababba aaabbbaaa aaabbbabaababb .
Esempi di linguaggi formali su A sono:
* il linguaggio di tutte le stringhe che contengono lo stesso numero di a e di b;
* lo stesso insieme di tutte le parole su A e lo stesso insieme vuoto;
* l'insieme delle stringhe della forma an con n numero primo;
* l'insieme dei programmi in un dato linguaggio di programmazione che si dimostrano sintatticamente corretti;
* l'insieme delle stringhe che, immesse in una macchina di Turing, la fanno evolvere fino ad un arresto.
Un linguaggio formale può essere definito in una grande varietà di modi.
* come insieme delle stringhe derivate nell'ambito di una grammatica formale (v. gerarchia di Chomsky);
* stringhe fornite da un'espressione regolare;
* stringhe accettate da qualche automa, come una macchina di Turing o un automa a stati finiti;
* nell'ambito di un insieme di domande la cui risposta può essere solo SI o NO, le domande a risposta affermativa (v. problema di decisione).
I linguaggi si possono comporre con molte operazioni e in tal modo si possono ottenere molti linguaggi a partire da un insieme di linguaggi dati. Con L1 ed L2 denotiamo due linguaggi sopra un dato alfabeto.
* La concatenazione o giustapposizione L1L2 consiste di tutte le stringhe della forma vw dove v è una stringa di L1 e w una stringa di L2.
* L' intersezione di L1 ed L2 consiste di tutte le stringhe contenute sia in L1 che in L2.
* L' unione di L1 ed L2 consiste di tutte le stringhe che sono contenute in L1 o in L2.
* Il complemento del linguaggio L1 consiste di tutte le stringhe sopra l'alfabeto che non sono contenute in L1.
* Il quoziente destro L1/L2 di L1 da L2 consiste di tutte le stringhe v per le quali esiste una stringa w in L2 tale che vw si trova in L1.
* La star di Kleene L1* consiste di tutte le stringhe che possono essere scritte nella forma w1w2...wn con le stringhe wi in L1 ed n ≥ 0. Si noti che questo include la stringa muta in quanto si ammette n = 0.
* Il riflesso L1R contiene le stringhe riflesse, capovolte, di tutte le stringhe in L1.
* Il mescolamento o shuffle di L1 ed L2 consiste di tutte le stringhe che si possono scrivere nella forma v1w1v2w2...vnwn, dove n ≥ 1 and v1,...,vn sono stringhe tali che la concatenazione v1...vn si trova in L1 e w1,...,wn sono stringhe tali che w1...wn si trova L2."
Ovvio, no? No. Per un bel cazzo.
