^^Linguaggio formale.

le teorie sui linguaggio ... affascinanti, all'intersezione tra linguistica, matematica e informatica.

1956: The Chomsky hierarchy. L'articolo fondante i linguaggi formali

"Linguaggio" normalmente inteso e' il  linguaggio naturale

la caratteristica fondamentale del linguaggio naturale e' che comunica, cioe' ha un significato, cioe' una semantica

ref: Linguaggio: grammatica, semantica, sintassi.

"Linguaggio" in senso matematico e in teorie di linguistica

La differenza scioccante con la definizione matematica e le definizioni di teorie di linguistica, e' che

 

Language

  1. 1929 Bloomfield
    the totality of utterances that can be made in a speech community.
  2. 1956 Chomsky
    a numerable set of sentences, of finite length, constructed from a finite alphabet of symbols.
  3. 1965 Knuth
    a "set of strings", without regard to their meaning.

 

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.

Linguaggio dal semplice al complesso

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 "definire un linguaggio semplice"

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?

La grande fondamentale D&R

D: come generare un linguaggio?
R: tramite regole di riscrittura

R: 4 metodi per generare un linguaggio:

  1. Sistemi di riscrittura.
  2. Formal grammars.
  3. Regular expression.
  4. wp/Pattern_systems

Sapendo generare le stringhe, data una stringa

  1. appartiene al linguaggio? R: Recognizing
  2. come derivarla?  R: Parsing (partizionarla)

In estrema sintesi: Usare un linguaggio

≡ comporre e scomporre un testo secondo una regola

≡ codificare e decodificare.

es generarare in linguaggio tramite grammatica

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

es frasi generate

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.

nm: The strings of a language are also called

poiche' nel caso particolare sotto esame possono essere interpretate in questo modo.

The word problem (in algebra)

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

ref: The decision problem.

History. From Parsing timeline

  1. 1929 Language def, Boomfield
  2. 1956 Chomsky hierarchy. L'articolo fondante i linguaggi formali
  3. 1956 Language def, Chomsky
  4. 1957 Chomsky Syntactic Structures one of the most important books of all time
  5. 1965 Language def, Knuth
  6. 1965 The Parsing Problem

Alfabeto di un linguaggio formale.
Linguaggi di un alfabeto.

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:

  1. alfabeto l'insieme di elementi 
  2. caratteri gli elementi dell'insieme alfabeto.
string (over an alphabet)
a finite sequence of symbols of the alphabet.
finite sequence
include the empty sequence, that's the empty string ε

Σ 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

 

Approfond

D: cosa intendere "struttura di un linguaggio"?

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?

Links

  1. Linguistica. | Generative_grammar | Colorless_green_ideas_sleep_furiously

  2. Logica delle proposizioni. Calcolo delle proposizioni.
  3. Sistemi formali.

 

 

 

Talk

 

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

 

  1. identificatore  inizia con una lettera, eventualmente seguita da altre lettere o cifre.
  2. numero intero sequenza di cifre

 

Di solito si trova detto "linguaggi formali", ma io preferisco il singolare "linguaggio formale"

 

La grande fondamentale idea-ambizione e'

definire la struttura di un linguaggio tramite regole di riscrittura

 

Linguaggio, definizione  estensiva o intensiva

, 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.

 

  1. >>> 1929 Language def, Boomfield

  2. >>> 1956 Chomsky hierarchy. L'articolo fondante i linguaggi formali
  3. >>> 1956 Language def, Chomsky
  4. >>> 1957 Chomsky Syntactic Structures one of the most important books of all time
  5. >>> 1965 Language def, Knuth
  6. >>> 1965 The Parsing Problem