le teorie sui linguaggio ... affascinanti, all'intersezione tra linguistica, matematica e informatica.
1956: The Chomsky hierarchy. L'articolo fondante i linguaggi formali
la caratteristica fondamentale del linguaggio naturale e' che comunica, cioe' ha un significato, cioe' una semantica
ref: Linguaggio: grammatica, semantica, sintassi.
La differenza scioccante con la definizione matematica e le definizioni di teorie di linguistica, e' che
Language
Formal language a set of strings.
A formal language is defined without reference to the meanings of its expressions; it can exist before any interpretation is assigned to it — that is, before it has any meaning.
A language that can be described by a body of rules.
Definire un linguaggio come "insieme di stringhe" e' comodo e sensato poiche' e' inclusivo di tutti i casi, dal piu' semplice al piu' complesso,
es: "Rispondere alle domande con SI o NO"
si puo'
formalizzare dicendo che:
"il linguaggio da usare nella risposta e' {SI, NO}".
es: 2 linguaggi sull'alfabeto binario {0, 1}
L1 = {0, 01, 0101, 01100110}
L2 = {0n1n | n>0} = {01, 0011, 000111, 00001111, ...}
L1 ha 4 frasi, L2 e' infinito.
La stringa 01 e' in entrambi i linguaggi, invece le altre no.
ma come definire un linguaggio complesso, es produrre le frasi del linguaggio naturale?
D: come generare un linguaggio?
R: tramite regole di
riscrittura
Sapendo generare le stringhe, data una stringa
In estrema sintesi: Usare un linguaggio
≡ comporre e scomporre un testo secondo una regola
≡ codificare e decodificare.
frase= GN + GV gruppo nominale + gruppo verbale
GN = N | N+A nome, oppure nome + aggettivo
GV = V | V+AV | V+C | V+AV+C verbo, o verbo + avverbio
o verbo + complemento, o verbo + avverbio + complemento
Il gatto mangiò. GN+GV → nome+verbo
Il gatto affamato mangiò. GN+GV → (nome+aggettivo)+verbo
Il gatto mangiò velocemente. GN+GV → nome+(verbo+avverbio)
Il gatto mangiò il suo pasto. GN+GV → nome+(verbo+complemento)
Il gatto affamato mangiò velocemente il suo pasto.
poiche' nel caso particolare sotto esame possono essere interpretate in questo modo.
to decide whether two strings of symbols are equivalent given a set of algebraic rules.
es: 2 espressioni algebriche letterali sono equivalenti?
ref: johndcook/the-word-problem | why-is-the-word-problem-hard
Per chi piace la forma e' una grande e fantastica costruzione.
Si parte proprio da zero, dalle basi della teoria degli insiemi:
E' tutto. In tale contesto, i nomi sono:
Σ⋆ the set of all the strings over the alphabet Σ
this use of the asterisk is known as the Kleene star or Kleene
closure, after Stephen Kleene. ref: wp/Kleene_star
Σ={a} Σ⋆ = {ε, a, aa, aaa, …}
Σ={a, b} Σ⋆ = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, …}
ak 'a' repeated k times. es: a3=aaa; a0=ε the empty string
{an ∣ n > 0} = {a, aa, aaa, …}
{an ∣ n ≥ 0} = {ε, a, aa, aaa, …}
well-formed formula (of a language) ≡ wff ≡ formula ≡ word (of the language) ≡ sentence (of the language)
I diversi nomi per lo stesso concetto rispecchiano i diversi contesti d'uso.
Per fissare le idee consideriamo le "espressioni con le 4 operazioni dell'aritmetica" o le "formule algebriche", in questo contesto le strighe generate con
sono usualmente chiamate "espressioni" o "formule".
L'insieme Σ⋆ di tutte le possibili stringhe di caratteri e' allora l'insieme di tutte le possibili potenziali formule, poiche' sono tutte le sequenze che si possono scrivere coi simboli con cui si scrivono le formule; pero'
solo alcune saranno "formule ben formate" cioè effettivamente calcolabili, la gran maggioranza saranno "malformate": somiglianti a una formula poiche' costituita dagli stessi simboli, ma senza le regole che permettono di calcolarla.
Pero'
wp/Asterisk
the asterisk is used in regular expressions to denote zero or more repetitions of a pattern
D: come definire la struttura di un linguaggio?
D: Come generare-rappresentare un linguaggio?
D: come definire le regole per generare le frasi del linguaggio?
D: Quali sono i sistemi per definire un'ampia classe di linguaggi?
Linguistica. | Generative_grammar | Colorless_green_ideas_sleep_furiously
You can talk about readability all you like, but readability depends first and foremost on recognizability. Perl is very much a What-You-See-Is-What-It-Does language. linuxjournal
Di solito si trova detto "linguaggi formali", ma io preferisco il singolare "linguaggio formale"
definire la struttura di un linguaggio tramite regole di riscrittura
, che non sia l'appartenenza delle parole-frasi ad un elenco, altrimenti
sarebbe un camuffare la def estensiva da intensiva.
Nel caso di un nr infinito di parole, la def puo' essere solo intensiva.ref: Definizione
intensiva/estensiva.
>>> 1929 Language def, Boomfield