Differenze tra le versioni di "Linguaggi formali ed automi Turno 1/2005-2006"

Da WikiDsy.
(→‎Obiettivi e finalità didattiche)
m
 
(26 versioni intermedie di 4 utenti non mostrate)
Riga 1: Riga 1:
 +
[[Categoria:Corsi 2005-2006]]
 +
 
'''Linguaggi formali ed automi''' (per gli amici '''LFA''') è un '''insegnamento fondamentale''' del '''secondo anno''' per il corso di laurea in '''Informatica'''.
 
'''Linguaggi formali ed automi''' (per gli amici '''LFA''') è un '''insegnamento fondamentale''' del '''secondo anno''' per il corso di laurea in '''Informatica'''.
 
Può essere inserito nel piano di studi, come '''complementare esterno''' al corso di laurea, anche dagli studenti dei corsi di '''Informatica per le telecomunicazioni''', '''Comunicazione digitale''' e dagli studenti delle '''lauree specialistiche''' che non hanno sostenuto l'esame durante la triennale.
 
Può essere inserito nel piano di studi, come '''complementare esterno''' al corso di laurea, anche dagli studenti dei corsi di '''Informatica per le telecomunicazioni''', '''Comunicazione digitale''' e dagli studenti delle '''lauree specialistiche''' che non hanno sostenuto l'esame durante la triennale.
Riga 5: Riga 7:
  
 
{| border=1 cellspacing=0 cellpadding=1
 
{| border=1 cellspacing=0 cellpadding=1
−
| Nome dell'insegnamento || Linguaggi formali e automi
+
| Nome dell'insegnamento || '''Linguaggi formali e automi'''
 
|-
 
|-
−
| Corsi di laurea || Informatica
+
| Corsi di laurea || '''Informatica'''
 
|-
 
|-
−
| Categoria || Fondamentale
+
| Categoria || '''Fondamentale'''
 
|-
 
|-
−
| Anno || Secondo
+
| Anno || '''Secondo'''
 
|-
 
|-
−
| Semestre || Secondo
+
| Semestre || '''Secondo'''
 
|-
 
|-
−
| Crediti || 6.0 CFU  
+
| Crediti || '''6.0 CFU'''
 
|-
 
|-
−
| Turni || 2
+
| Turni || '''2'''
 
|-
 
|-
−
| Settore disciplinare || INF/01 Informatica
+
| Settore disciplinare || '''INF/01 Informatica'''
 
|-
 
|-
−
| Ore di didattica || 50
+
| Ore di didattica || '''50'''
 
|-
 
|-
−
| Frequenza || Consigliata
+
| Frequenza || '''Consigliata'''
 
|-
 
|-
 
| Scheda del corso || http://www.dico.unimi.it/occorrenza.php?z=0;id_occ=1057
 
| Scheda del corso || http://www.dico.unimi.it/occorrenza.php?z=0;id_occ=1057
Riga 29: Riga 31:
  
  
−
=== Docenti ===
+
=== Docente ===
  
 
Per gli studenti del turno 1 è responsabile del corso la professoressa '''Beatrice Palano'''.
 
Per gli studenti del turno 1 è responsabile del corso la professoressa '''Beatrice Palano'''.
 +
  
 
{| border=1 cellspacing=0 cellpadding=1
 
{| border=1 cellspacing=0 cellpadding=1
 
| Scheda personale || http://www.dico.unimi.it/persona.php?z=0;id_persona=259
 
| Scheda personale || http://www.dico.unimi.it/persona.php?z=0;id_persona=259
 
|-
 
|-
−
| E-mail || palano@dsi.unimi.it
+
| E-mail || [mailto:palano@dsi.unimi.it palano@dsi.unimi.it]
 
|-
 
|-
 
| Sito web personale || http://homes.dsi.unimi.it/~palano/  
 
| Sito web personale || http://homes.dsi.unimi.it/~palano/  
 
|-
 
|-
−
| Telefono || 0250316254
+
| Telefono || '''0250316254'''
 
|-
 
|-
−
| Fax || 0250316276
+
| Fax || '''0250316276'''
 
|}
 
|}
  
Riga 48: Riga 51:
 
=== Orario delle lezioni ===
 
=== Orario delle lezioni ===
  
−
Per l'A.A. 2005/2006 l'inizio delle lezioni è fissato per il '''7 marzo''' e il termine è previsto per l''''8 giugno'''.
+
{| border=1 cellspacing=0 cellpadding=1
 +
! Giorno !! Ora !! Luogo
 +
|-
 +
| Martedì || 10.30 - 12.30 || Aula 405 (Settore didattico, Via Celoria)
 +
|-
 +
| Giovedì || 11.30 - 13.30 || Aula 307 (Settore didattico, Via Celoria)
 +
|}
 +
 
 +
 
 +
Per l'A.A. 2005/2006 l'inizio delle lezioni è fissato per il '''7 marzo''' e il termine è previsto per l' '''8 giugno'''.
 +
 
  
 
=== Orario di ricevimento ===
 
=== Orario di ricevimento ===
  
 
La professoressa riceve il '''giovedì''' in orario '''15.30-16.30''' presso la stanza '''S203''' (Via Comelico, II piano).
 
La professoressa riceve il '''giovedì''' in orario '''15.30-16.30''' presso la stanza '''S203''' (Via Comelico, II piano).
 +
  
 
=== Sito web del corso ===
 
=== Sito web del corso ===
  
−
Qui il sito ufficiale del corso: http://homes.dsi.unimi.it/~palano/cur/lfa.html
+
Qui il sito ufficiale del corso: http://homes.dsi.unimi.it/~palano/lfa.html
  
 
=== Descrizione ===
 
=== Descrizione ===
  
−
Il corso è dedicato alla teoria dei linguaggi formali e degli automi.
+
Il corso è dedicato alla teoria dei [http://it.wikipedia.org/wiki/Linguaggio_formale_%28matematica%29 linguaggi formali] e degli [http://it.wikipedia.org/wiki/Automa_(informatica) automi].
 +
 
 
Un '''linguaggio formale''' è un linguaggio (di qualunque tipo) che può essere descritto per mezzo di precise regole matematiche, utilizzando una scrittura simbolica convenzionale.
 
Un '''linguaggio formale''' è un linguaggio (di qualunque tipo) che può essere descritto per mezzo di precise regole matematiche, utilizzando una scrittura simbolica convenzionale.
−
Un '''automa''' (o macchina astratta) è un modello utilizzato per descrivere e rappresentare un'entità che assume nel tempo diversi stati e configurazioni secondo una precisa sequenza (macchina a stati finiti). In altre parole è un dispositivo astratto che stabilisce una precisa relazione tra un dato di ingresso e un dato di uscita. Gli automi sono strettamente legati ai linguaggi formali, in quanto consentono di definire algoritmi riconoscitivi, cioè procedure in grado di riconoscere le parole di un linguaggio. Gli automi, più in generale, sono utilizzati per rappresentare una qualsiasi procedura a stati finiti (0 algoritmo o computazione). Gli automi sono utili anche per rappresentare modelli astratti di calcolatori.
+
 
−
La teoria degli automi e dei linguaggi formali è alla base della descrizione dei linguaggi di programmazione e delle macchine calcolatrici, nonché una delle principali branche dell'informatica. Il suo studio è utile per la costruzione di compilatori, per la progettazione di nuovi linguaggi di programmazione e, in generale, per descrivere le caratteristiche di un linguaggio esistente, nonché per studiare e realizzare modelli astratti di calcolatore.
+
Un '''automa''' (o macchina astratta) è un modello utilizzato per descrivere e rappresentare un'entità che assume nel tempo diversi stati e configurazioni secondo una precisa sequenza (macchina a stati finiti). In altre parole è un dispositivo astratto che stabilisce una precisa relazione tra un dato di ingresso e un dato di uscita.
−
Molti dei concetti esposti possono essere approfonditi nel corso di [[Linguaggi_e_traduttori|Linguaggi e traduttori]].
+
 
 +
Gli automi sono strettamente legati ai linguaggi formali, in quanto consentono di definire algoritmi riconoscitivi, cioè procedure in grado di riconoscere le parole di un linguaggio. Gli automi, più in generale, sono utilizzati per rappresentare una qualsiasi procedura a stati finiti (o algoritmo o computazione). Gli automi sono utili anche per rappresentare modelli astratti di calcolatori.
 +
 
 +
La teoria degli automi e dei linguaggi formali è alla base della descrizione dei linguaggi di programmazione e delle macchine calcolatrici, nonché una delle principali branche dell'informatica.
 +
 
 +
Il suo studio è utile per la costruzione di compilatori, per la progettazione di nuovi linguaggi di programmazione e, in generale, per descrivere le caratteristiche di un linguaggio esistente, nonché per studiare e realizzare modelli astratti di calcolatore.
 +
 
 +
Molti dei concetti esposti possono essere approfonditi nel corso complemantare di [[Linguaggi_e_traduttori|Linguaggi e traduttori]].
 +
 
  
 
=== Obiettivi e finalità didattiche ===
 
=== Obiettivi e finalità didattiche ===
Riga 71: Riga 94:
  
 
Comprendere come descrivere una computazione e un modello di calcolatore.
 
Comprendere come descrivere una computazione e un modello di calcolatore.
 +
  
 
=== Argomenti trattati ===
 
=== Argomenti trattati ===
  
 
Linguaggi regolari e linguaggi liberi da contesto. Automi deterministici e non deterministici. Teorema di Kleene. Espressioni regolari. Forma normale di Chomsky. Formalismi BNF. Macchina di Turing. Il linguaggio XML.
 
Linguaggi regolari e linguaggi liberi da contesto. Automi deterministici e non deterministici. Teorema di Kleene. Espressioni regolari. Forma normale di Chomsky. Formalismi BNF. Macchina di Turing. Il linguaggio XML.
 +
  
 
=== Programma ===
 
=== Programma ===
 +
 +
Il programma del corso si compone di tre parti:
 +
* Concetti di base sui linguaggi
 +
** Linguaggi ricorsivi
 +
** Linguaggi ricorsivamente numerabili
 +
** Grammatiche (come esempio di sistema generativo)
 +
* Linguaggi regolari e Automi a stati finiti
 +
* Linguaggi liberi da contesto e Automi a pila
  
 
Il programma integrale è disponibile presso il sito web del corso.
 
Il programma integrale è disponibile presso il sito web del corso.
 +
  
 
=== Libro di testo e materiale didattico ===
 
=== Libro di testo e materiale didattico ===
Riga 87: Riga 121:
  
 
Nello stesso sito si consiglia il testo ''J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979''.
 
Nello stesso sito si consiglia il testo ''J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979''.
 +
  
 
=== Modalità d'esame ===
 
=== Modalità d'esame ===
  
 
E' prevista una sola '''prova orale''' a fine corso.
 
E' prevista una sola '''prova orale''' a fine corso.
 +
  
 
=== Calendario degli appelli ===
 
=== Calendario degli appelli ===
Riga 96: Riga 132:
 
Qui di seguito sono riportate le '''sessioni d'esame''' per l'A.A. 2005/2006 (a partire dalla prima prova utile di giugno):
 
Qui di seguito sono riportate le '''sessioni d'esame''' per l'A.A. 2005/2006 (a partire dalla prima prova utile di giugno):
  
−
* '''19 giugno 2006'''
+
* '''16 giugno 2006'''
 
* '''10 luglio 2006'''
 
* '''10 luglio 2006'''
 
* '''18 settembre 2006'''
 
* '''18 settembre 2006'''
Riga 108: Riga 144:
  
 
LFA è invece il prerequisito fondamentale per il corso di [[Linguaggi_e_traduttori|Linguaggi e traduttori]].
 
LFA è invece il prerequisito fondamentale per il corso di [[Linguaggi_e_traduttori|Linguaggi e traduttori]].
 +
  
 
=== Frequenza ===
 
=== Frequenza ===
Riga 113: Riga 150:
 
La '''frequenza''' al corso non è obbligatoria, ma comunque '''consigliata'''.
 
La '''frequenza''' al corso non è obbligatoria, ma comunque '''consigliata'''.
  
−
=== Altre informazioni ===
+
 
 +
=== Informazioni utili ===
  
 
* La professoressa ha sottolineato che il corso ha un taglio molto teorico (cosa potrebbe deludere le aspettative di alcuni studenti).
 
* La professoressa ha sottolineato che il corso ha un taglio molto teorico (cosa potrebbe deludere le aspettative di alcuni studenti).
 
* Il programma del corso e il materiale didattico sono identici per i due turni, ed è possibile essere ricevuti indifferentemente da entrambi i docenti (nei rispettivi orari).
 
* Il programma del corso e il materiale didattico sono identici per i due turni, ed è possibile essere ricevuti indifferentemente da entrambi i docenti (nei rispettivi orari).
  
−
=== Link utili ===
+
 
 +
 
 +
== Diario del corso A.A. 2005/2006 ==
 +
 
 +
=== Lezione 1 di martedì 7 marzo 2006 ===
 +
 
 +
* La professoressa ha introdotto il corso e illustrato le modalità d'esame, dopodiché ha avuto inizio la lezione vera e propria.
 +
 
 +
''N.B. Per affrontare questa prima parte è necessario avere familiarità con il linguaggio algebrico di base e con l'insiemistica. Inoltre verranno richiamati alcuni concetti già affrontati nel corso di matematica discreta, come il concetto di Monoide''.
 +
 
 +
* A partire dal titolo del corso '''Linguaggi formali e automi''', sono state date le definizioni di:
 +
** '''Linguaggio''': ''"Insieme di frasi che consente la comunicazione di più entità"''.
 +
*** Esempi di linguaggio:
 +
**** Linguaggio naturale (esempio: ''lingua italiana'').
 +
**** Linguaggio di programmazione (esempio: ''linguaggio C'').
 +
** '''Linguaggio formale''': ''"Linguaggio specificato in maniera rigorosa attraverso strumenti matematici e caratterizzato da un numero finito di regole" (ha quindi la possibilità di essere "trattati" da un calcolatore)''.
 +
*** '''Strumenti generativi'''.
 +
*** '''Strumenti riconoscitivi'''.
 +
** '''Automa''': ''"Macchina astratta in grado di descrivere alcuni tipi di linguaggi" (nello specifico i linguaggi formali)''.
 +
* Esempi di linguaggi formali ''(linguaggi di programmazione)'' e di linguaggi non formali ''(linguaggio naturale)''.
 +
* Concetti base della teoria dei linguaggi formali:
 +
** '''Simboli'''.
 +
** '''Alfabeto''': ''"Si definisce alfabeto un insieme finito di simboli"''.
 +
*** Esempi di alfabeto:
 +
**** '''Alfabeto unario'''.
 +
**** '''Alfabeto binario'''.
 +
** '''Parola''': ''"Si definisce parola una sequenza finita di simboli appartenenti all'alfabeto"''.
 +
*** Esempi.
 +
** '''Parola vuota''': ''"Parola costituita da zero simboli dell'alfabeto"''.
 +
** '''Lunghezza''' di una parola: ''"Numero di simboli (distinti per posizione) che compongono la parola" (il termine "distinti per posizione" significa semplicemente che un simbolo che compare più volte nella parola, viene conteggiato più volte)''.
 +
** '''Insieme di tutte le parole''': definizione matematica.
 +
** '''Insieme di tutte le parole meno la parola vuota''': definizione matematica.
 +
** Relazioni insiemistiche tra questi due insiemi.
 +
* Operazioni sulle parole:
 +
** '''Prodotto''' (o '''concatenazione'''): ''"Date due parole x e y, con x di lunghezza n e y di lunghezza m, il prodotto |x y| è ancora una parola, di lunghezza n + m, formata da i simboli di x seguiti dai simboli di y"''.
 +
** Proprietà del prodotto:
 +
*** La proprietà associativa.
 +
*** L'elemento neutro (costituito dalla parola vuota).
 +
*** Proprietà commutativa (solo nel caso di alfabeto unario)
 +
* Il '''monoide libero''' generato dall'alfabeto.
 +
* '''Sottoparole''':
 +
** '''Fattore''': ''simbolo che, all'interno della parola, è preceduto da un altro o più simboli (prefisso) e seguito da un altro o più simboli (suffisso)''; definizione matematica.
 +
** '''Prefisso''': definizione matematica.
 +
** '''Suffisso''': definizione matematica.
 +
** Esempi.
 +
* Definizione matematica di linguaggio formale: ''"Un linguaggio formale L è un insieme di parole che utilizzano un alfabeto ed è sottoinsieme dell'insieme di tutte le parole"''.
 +
* '''Linguaggi finiti''' e '''linguaggi infiniti'''.
 +
* Casi particolari:
 +
** '''Linguaggio vuoto''': ''linguaggio privo di parole''.
 +
** '''Linguaggio contenente la parola vuota''': ''linguaggio composto da una parola (la parola vuota)''.
 +
* Esempi di linguaggi infiniti: il codice binario e altri.
 +
 
 +
== Avvisi per gli studenti ==
 +
 
 +
 
 +
== Risorse esterne ==
  
 
* Materiale didattico sul web:
 
* Materiale didattico sul web:
Riga 134: Riga 227:
 
** [http://www.dico.unimi.it/files/occorrenza/programma/programma387804.pdf Programma A.A. 2003/2004]
 
** [http://www.dico.unimi.it/files/occorrenza/programma/programma387804.pdf Programma A.A. 2003/2004]
 
** [http://www.dico.unimi.it/files/occorrenza/programma/programma404976.pdf Programma A.A. 2002/2003]
 
** [http://www.dico.unimi.it/files/occorrenza/programma/programma404976.pdf Programma A.A. 2002/2003]
−
 
−
== Diario del corso A.A. 2005/2006 ==
 
−
 
−
== Avvisi per gli studenti ==
 

Versione attuale delle 17:04, 2 ago 2006


Linguaggi formali ed automi (per gli amici LFA) è un insegnamento fondamentale del secondo anno per il corso di laurea in Informatica. Può essere inserito nel piano di studi, come complementare esterno al corso di laurea, anche dagli studenti dei corsi di Informatica per le telecomunicazioni, Comunicazione digitale e dagli studenti delle lauree specialistiche che non hanno sostenuto l'esame durante la triennale.

Informazioni generali

Nome dell'insegnamento Linguaggi formali e automi
Corsi di laurea Informatica
Categoria Fondamentale
Anno Secondo
Semestre Secondo
Crediti 6.0 CFU
Turni 2
Settore disciplinare INF/01 Informatica
Ore di didattica 50
Frequenza Consigliata
Scheda del corso http://www.dico.unimi.it/occorrenza.php?z=0;id_occ=1057


Docente

Per gli studenti del turno 1 è responsabile del corso la professoressa Beatrice Palano.


Scheda personale http://www.dico.unimi.it/persona.php?z=0;id_persona=259
E-mail palano@dsi.unimi.it
Sito web personale http://homes.dsi.unimi.it/~palano/
Telefono 0250316254
Fax 0250316276


Orario delle lezioni

Giorno Ora Luogo
Martedì 10.30 - 12.30 Aula 405 (Settore didattico, Via Celoria)
Giovedì 11.30 - 13.30 Aula 307 (Settore didattico, Via Celoria)


Per l'A.A. 2005/2006 l'inizio delle lezioni è fissato per il 7 marzo e il termine è previsto per l' 8 giugno.


Orario di ricevimento

La professoressa riceve il giovedì in orario 15.30-16.30 presso la stanza S203 (Via Comelico, II piano).


Sito web del corso

Qui il sito ufficiale del corso: http://homes.dsi.unimi.it/~palano/lfa.html

Descrizione

Il corso è dedicato alla teoria dei linguaggi formali e degli automi.

Un linguaggio formale è un linguaggio (di qualunque tipo) che può essere descritto per mezzo di precise regole matematiche, utilizzando una scrittura simbolica convenzionale.

Un automa (o macchina astratta) è un modello utilizzato per descrivere e rappresentare un'entità che assume nel tempo diversi stati e configurazioni secondo una precisa sequenza (macchina a stati finiti). In altre parole è un dispositivo astratto che stabilisce una precisa relazione tra un dato di ingresso e un dato di uscita.

Gli automi sono strettamente legati ai linguaggi formali, in quanto consentono di definire algoritmi riconoscitivi, cioè procedure in grado di riconoscere le parole di un linguaggio. Gli automi, più in generale, sono utilizzati per rappresentare una qualsiasi procedura a stati finiti (o algoritmo o computazione). Gli automi sono utili anche per rappresentare modelli astratti di calcolatori.

La teoria degli automi e dei linguaggi formali è alla base della descrizione dei linguaggi di programmazione e delle macchine calcolatrici, nonché una delle principali branche dell'informatica.

Il suo studio è utile per la costruzione di compilatori, per la progettazione di nuovi linguaggi di programmazione e, in generale, per descrivere le caratteristiche di un linguaggio esistente, nonché per studiare e realizzare modelli astratti di calcolatore.

Molti dei concetti esposti possono essere approfonditi nel corso complemantare di Linguaggi e traduttori.


Obiettivi e finalità didattiche

Apprendere i concetti fondamentali della teoria degli automi e dei linguaggi formali, nonché il loro utilizzo per l'analisi, la descrizione e la compilazione dei linguaggi di programmazione.

Comprendere come descrivere una computazione e un modello di calcolatore.


Argomenti trattati

Linguaggi regolari e linguaggi liberi da contesto. Automi deterministici e non deterministici. Teorema di Kleene. Espressioni regolari. Forma normale di Chomsky. Formalismi BNF. Macchina di Turing. Il linguaggio XML.


Programma

Il programma del corso si compone di tre parti:

  • Concetti di base sui linguaggi
    • Linguaggi ricorsivi
    • Linguaggi ricorsivamente numerabili
    • Grammatiche (come esempio di sistema generativo)
  • Linguaggi regolari e Automi a stati finiti
  • Linguaggi liberi da contesto e Automi a pila

Il programma integrale è disponibile presso il sito web del corso.


Libro di testo e materiale didattico

Non è stato consigliato alcun libro di testo.

Il materiale didattico di riferimento adottato consiste in una serie di dispense (un documento in 3 parti), disponibili presso il sito web del corso.

Nello stesso sito si consiglia il testo J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.


Modalità d'esame

E' prevista una sola prova orale a fine corso.


Calendario degli appelli

Qui di seguito sono riportate le sessioni d'esame per l'A.A. 2005/2006 (a partire dalla prima prova utile di giugno):

  • 16 giugno 2006
  • 10 luglio 2006
  • 18 settembre 2006
  • 15 gennaio 2007

Le date successive sono ancora da stabilire.

Prerequisiti

Sono prerequisiti per il corso di LFA i fondamenti essenziali della programmazione, le nozioni fondamentali dell'insiemistica e la conoscenza del linguaggio algebrico di base.

LFA è invece il prerequisito fondamentale per il corso di Linguaggi e traduttori.


Frequenza

La frequenza al corso non è obbligatoria, ma comunque consigliata.


Informazioni utili

  • La professoressa ha sottolineato che il corso ha un taglio molto teorico (cosa potrebbe deludere le aspettative di alcuni studenti).
  • Il programma del corso e il materiale didattico sono identici per i due turni, ed è possibile essere ricevuti indifferentemente da entrambi i docenti (nei rispettivi orari).


Diario del corso A.A. 2005/2006

Lezione 1 di martedì 7 marzo 2006

  • La professoressa ha introdotto il corso e illustrato le modalità d'esame, dopodiché ha avuto inizio la lezione vera e propria.

N.B. Per affrontare questa prima parte è necessario avere familiarità con il linguaggio algebrico di base e con l'insiemistica. Inoltre verranno richiamati alcuni concetti già affrontati nel corso di matematica discreta, come il concetto di Monoide.

  • A partire dal titolo del corso Linguaggi formali e automi, sono state date le definizioni di:
    • Linguaggio: "Insieme di frasi che consente la comunicazione di più entità".
      • Esempi di linguaggio:
        • Linguaggio naturale (esempio: lingua italiana).
        • Linguaggio di programmazione (esempio: linguaggio C).
    • Linguaggio formale: "Linguaggio specificato in maniera rigorosa attraverso strumenti matematici e caratterizzato da un numero finito di regole" (ha quindi la possibilità di essere "trattati" da un calcolatore).
      • Strumenti generativi.
      • Strumenti riconoscitivi.
    • Automa: "Macchina astratta in grado di descrivere alcuni tipi di linguaggi" (nello specifico i linguaggi formali).
  • Esempi di linguaggi formali (linguaggi di programmazione) e di linguaggi non formali (linguaggio naturale).
  • Concetti base della teoria dei linguaggi formali:
    • Simboli.
    • Alfabeto: "Si definisce alfabeto un insieme finito di simboli".
      • Esempi di alfabeto:
        • Alfabeto unario.
        • Alfabeto binario.
    • Parola: "Si definisce parola una sequenza finita di simboli appartenenti all'alfabeto".
      • Esempi.
    • Parola vuota: "Parola costituita da zero simboli dell'alfabeto".
    • Lunghezza di una parola: "Numero di simboli (distinti per posizione) che compongono la parola" (il termine "distinti per posizione" significa semplicemente che un simbolo che compare più volte nella parola, viene conteggiato più volte).
    • Insieme di tutte le parole: definizione matematica.
    • Insieme di tutte le parole meno la parola vuota: definizione matematica.
    • Relazioni insiemistiche tra questi due insiemi.
  • Operazioni sulle parole:
    • Prodotto (o concatenazione): "Date due parole x e y, con x di lunghezza n e y di lunghezza m, il prodotto |x y| è ancora una parola, di lunghezza n + m, formata da i simboli di x seguiti dai simboli di y".
    • Proprietà del prodotto:
      • La proprietà associativa.
      • L'elemento neutro (costituito dalla parola vuota).
      • Proprietà commutativa (solo nel caso di alfabeto unario)
  • Il monoide libero generato dall'alfabeto.
  • Sottoparole:
    • Fattore: simbolo che, all'interno della parola, è preceduto da un altro o più simboli (prefisso) e seguito da un altro o più simboli (suffisso); definizione matematica.
    • Prefisso: definizione matematica.
    • Suffisso: definizione matematica.
    • Esempi.
  • Definizione matematica di linguaggio formale: "Un linguaggio formale L è un insieme di parole che utilizzano un alfabeto ed è sottoinsieme dell'insieme di tutte le parole".
  • Linguaggi finiti e linguaggi infiniti.
  • Casi particolari:
    • Linguaggio vuoto: linguaggio privo di parole.
    • Linguaggio contenente la parola vuota: linguaggio composto da una parola (la parola vuota).
  • Esempi di linguaggi infiniti: il codice binario e altri.

Avvisi per gli studenti

Risorse esterne

Estratto da "https://wiki.dsy.it/index.php?title=Linguaggi_formali_ed_automi_Turno_1/2005-2006&oldid=14748"