^^Linguaggio formale.


  1. the totality of utterances that can be made in a speech community.

    1929 Bloomfield >>>

    Note: no reference to semantics, the language usual view:
    utterances of a language "mean" something.

  2. a numerable set of sentences, of finite length, constructed from a finite alphabet of symbols.

    1956 Chomsky >>>

    This is exactly Bloomfield's definition, restated using set theory.

    Chomsky's model produces multiple syntactic derivations of the same sentence, this "looks" like the meanings of an ambiguous sentence.

  3. a "set of strings", without regard to their meaning.

    1965 Knuth >>>

    The Bloomfieldian definition, while severely restrictive, has yet to cause any recognizable harm.

Formal language

a language that can be described by a body of systematic rules, a formal grammar.

A language 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.

First order logic is expressed in some formal language.

Linguaggio, definizione

La grande idea-ambizione

definire un linguaggio tramite un insieme di regole

Questioni fondamentali, e Risposta

  1. Representation of Languages

    come definire le regole per generare le parole-frasi del linguaggio.
    Can we find systematic methods for defining rules that characterize a wide class of languages?

    R: 3 methods are: regular expressions, pattern systems, and Formal grammars.


  2. data una stringa
    1. appartiene al linguaggio? R: Recognizing
    2. come generarla?
      R: Parsing ≡ construction history ≡ derivation history.

In estrema sintesi: comporre e scomporre un testo secondo una regola. Codificare decodificare.

Es linguaggi

The sets  L1 = {01; 11; 0110}   L2 = {0n1n | n>0}

are two languages over the binary alphabet {0; 1}.

L1 has 3 words, L2 is infinite.

The string 01 is in both languages, while 11 is in L1 but not in L2.

The strings of a language are also called

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


The word problem




Per chi piace la forma e' una grande e fantastica costruzione.

Si parte proprio da zero, dalle basi della teoria degli insiemi: un insieme di elementi, finito e non vuoto. E' tutto.

Dato il contesto:

  1. alfabeto l'insieme di elementi 
  2. caratteri gli elementi dell'insieme alfabeto.
  3. stringa successione finita di caratteri
  4. identificatore  inizia con una lettera, eventualmente seguita da altre lettere o cifre.
  5. numero intero sequenza di cifre

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

Increasing generality of languages:

regular < context-free < context-sensitive < recursively enumerable


You can talk about readability all you like, but readability depends first and foremost on recognizability. linuxjournal


  1. Linguistica. | Generative_grammar | Colorless_green_ideas_sleep_furiously

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

ing: formal language



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