Linguaggi formali e automi

Name: Linguaggi formali e automi
Rating: 3.0 (1 reviews)
Author: Sbr3giuz

Revisionato il 25/07/2026

di Sbr3giuz

Publisher

Vota 3,0/5 (1)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Appunti presi a lezione e ristrutturati in bella copia su carta per l'esame di Linguaggi formali e automi basati su appunti personali del publisher presi alle lezioni della prof. Palano …

Esame Linguaggi formali autonomi

Facoltà Scienze matematiche fisiche e naturali

Dal corso del Prof. Palano Beatrice

Università Università degli Studi di Milano

A.A. 2021-2022

69 pagine

1 download

Appunto

Scarica

Estratto del documento

Ciao! Sono Federico Tabellini

Ciao! Sono Federico Tabellini, l'autore di questi appunti.

Siccome mi rendo conto che a volte la mia scrittura può non essere chiara e immediata ti lascio la mia mail dove puoi contattarmi per chiedermi di trascriverti una frase/parola che non riesci a leggere.

Indica nell'oggetto il nome della materia oppure mandami uno screen specificando la parola.

Non appena potrò risponderò alla tua mail.

fede.tabellini@gmail.com

NB: Non spiego concetti, traduco e basta.

Un buon quaderno di appunti deve comunque essere accompagnato da studio e pazienza.

Accetto consigli / critiche (solo se costruttive).

Spero che questi appunti ti aiutino.

Buono studio.

Ciao! Sono Federico Tabellini

Ciao! Sono Federico Tabellini, l'autore di questi appunti.

Indica nell'oggetto il nome della materia oppure mandami uno screen specificando la parola.

Non appena potrò risponderò alla tua mail.

fede.tabellini@gmail.com

NB: Non spiego concetti, traduco e basta.

Un buon quaderno di appunti deve comunque essere accompagnato da studio e pazienza.

Accetto consigli/critiche (solo se costruttive).

Spero che questi appunti ti aiutino.

Buono studio.

Linguaggi formali e automi

Introduzione

Insiemi di protocolli che permettono la comunicazione.

Esempi:

Linguaggi naturali → comunicazione tra individui.
Linguaggi di programmazione → comunicazione uomo macchina.
Segnaletica stradale.
Codice Morse.

Come insegnare un linguaggio?

Prima spieghiamo il lessico: (forniamo un vocabolario).

Spiegazione sintattica (come formare frasi corrette): (forniamo regole grammaticali).

Formale: aspetti che permettono di dare specifiche espressioni di un linguaggio.

Pro: poter tradurre i linguaggi in maniera automatica (senza intervento diretto dell’uomo).

Esempio: compilatori.

Verificano sintassi e lessico di un programma e stabiliscono la traduzione in linguaggi macchina (.exe).

Linguaggi naturali

Linguaggi naturali: sono più complessi e si dividono in:

Parlato.
Viene usato vocabolaria pre.
Vengono usate parole.
Si creano compiti programmi (verbi, soggetti, articoli).
Scritto.
Messaggi: sequenza di caratteri (compresi spazi e punteggiatura).

Sottoparagrafo

Sottoparagrafo: consiste in un sottoinsieme di un linguaggio (numero di messaggi predefinito) per condurre trattabili in maniera automatica.

Esempio: traduttori automatici (insoddisfacenti per la maggior parte dei casi).

Tecniche per la specifica formale dei linguaggi

Per la specifica formale dei linguaggi si usano due tecniche:

Sistemi generativi ➔ insiemi di regole per scrivere frasi di senso compilato (vocaboli e grammatica regole) generando tutte le possibili frasi del linguaggio es: grammatiche.
Sistemi riconoscitivi ➔ macchina che stabilisce quali frasi sono corrette o meno (output input/macchina) dato in input un messaggio es: automi: (sistema in grado di compiere operazioni predefinite).

Concetti centrali nella teoria dei linguaggi formali

Concetti centrali nella teoria dei linguaggi formali:

Alfabeto: insieme di simboli che ci permettono di costruire le parole di un linguaggio.

Σ = {d₁, d₂, d₃ ... d_k} ➔ k = numero di simboli di un alfabeto.

Parola su Σ: sequenza di simboli di Σ distribuiti per posizione.

Es: Σ = {0,1} ➔ parole possibili: ϖ² = aa aϖ = a aϖϖ = aϖϖ Σ = {0,1,4} Σ = {A,C,T,G} ➔ parola di circa 10⁶ simboli di Σ (alfabeto "DNA").

→ Una parola (ω) è un numero finito di simboli.

Lunghezza di una parola: numero di simboli che compongono la parola.

ω = ϖϖϖ ➔ |ω| = 2.

Una parola con lunghezza = 0 è definita parola vuota (ε).

Σ^* = insieme delle parole componibili dallo Σ compresa ε.

Σ⁺ = insieme delle parole componibili dallo Σ esclusa ε (⇔ Σ⁺ = Σ^*\{ε}).

∘ Prodotto di giustapposizione: concatenazione di più parole per formare una frase.

Si indica con:

Esempio.

Anteprima

Vedrai una selezione di 15 pagine su 69