Esame Fondamenti di informatica

P(

L’insieme di tutti i linguaggi si denota con

Operazioni su linguaggi

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Concatenazione linguaggi ∗ ∗ ∗

) ) )

_ . ( × ( → (

Come per le stringhe, la funzione di concatenazione sui linguaggi è definita

Per tutti i linguaggi dell’alfabeto essa è definita così:

Esempio:

Concatenazione n-aria ∗

),

L ∈ (

Dato un insieme A e il linguaggio ogni numero naturale è definito induttivamente così:

0

=

1. (clausola base) +1

= L ∙

2. (clausola induttiva)

Esempio:

Stella di Kleene

∗ ∗ ∗ ∗

( ) ) ) )

: P( → ( L ∈ (

Funzione definita per tutti i linguaggi nel seguente modo:

⋆ n

L = L

⋃

n∈ N

Esempio:

Automi

Tipologia di macchina a stati, prende in input una strina, che analizza carattere per carattere, fino a quando

incontra un determinato carattere per cui è previsto il “passaggio di stato”.

(,

, = , ):

Dato un alfabeto l’automa è una tripla

➢ è un insieme, detto INSIEME DEGLI STATI;

➢ (

⊆ × ) × ( × , )

è una relazione detta RELAZIONE DI TRANSIZIONE,

∈ ∈

associa a ogni elemento e ogni stato di stato di partenza zero o più stati di arrivo.

➢ ⊆ è l’insieme degli STATI FINALI (anche detti stati di accettazione).

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Esempio di transizione dell’automa sopra:

Raggiungibilità (,

= , ), ∈

Dato un automa per ogni elemento definiamo la sua transizione:

= {(, ) ∣ ), ) ∈ } ∈ (, )

((,

⋆

∈ ∈ (, )

Per ogni stringa , la relazione è definita induttivamente così:

=

1. (clausola base) ε

= ;

2. (clausola induttiva) (,

, ) ∈

Uno stato y è raggiungibile da x, quando esso si raggiunge attraverso la stringa cioè

Linguaggio accettato ⋆ )

⟨⟨⋅⟩⟩: → ( ∈

In un automa, la funzione è definita per ogni stato dell’automa come:

⋆ (,

⟨⟨⟩⟩ = { ∈ ∣ ∈ ℎ ) ∈ }}

⟨⟨⟩⟩

Un linguaggio può:

• ∈ ⟨⟨⟩⟩ ,

accettare la stringa in

• ∉ ⟨⟨ ⟩⟩ .

non accettare la stringa in

Determinismo Automa (, ) ∈ .

Le relazioni di transizione sono delle funzioni, associano a ogni coppia uno stato di arrivo

, .

Dato uno stato qualsiasi e un simbolo qualsiasi si transisce esattamente in uno stato

Si possono avere due tipi di algoritmi:

❖ Deterministico: la relazione di transizione è totale e univalente, è quindi una funzione

ogni elemento ha uno stato nel quale transire.

❖ Non Deterministico: la relazione di transizione non è una funzione (no totale e/o no univalente)

degli elementi non sono considerati o non hanno uno stato dove transire.

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Grammatiche libere da contesto

Permettono di descrivere i linguaggi, generando stringhe in modo ricorsivo, come fossero produzioni.

Un possibile esempio è la grammatica libera rappresentante le espressioni aritmetiche.

• ⟨⟩ ⟨⟩,

Categorie sintattiche: sono i simboli come o essi denotano i linguaggi,

• Metasimbolo: si legge come “può essere”,

• (+, − , × , ÷)

Simboli terminali: sono i simboli dell’alfabeto generato

La grammatica libera da contesto è quindi una coppia così formata:

:

- insieme simboli non terminali,

:

- insieme delle produzioni.

La grammatica è finita, quando l’insieme dei simboli terminali è finito.

Albero di derivazione sintattica

E’ un albero radicato utilizzato per rappresentare graficamente la derivazione di una grammatica.

➢ Ogni nodo interno è etichettato da un simbolo non terminale,

➢ Ogni foglia è etichettato un simbolo terminale,

➢

Ogni nodo interno è l’applicazione di una produzione tale che:

- l’etichetta del nodo è la testa della produzione,

- l’etichetta dei figli di v formano il corpo della produzione.

Ambiguità ⋆

ω ∈

Data una grammatica e una stringa , essa si dice:

▪ ():

Stringa ambigua per grammatica quando si hanno più alberi di derivazione possibili,

▪ Grammatica ambigua: quando ha almeno una stringa ambigua.

Per ovviare al problema, è necessario introdurre delle regole di precedenza sugli operatori.

Espressioni regolari

Con regolare vengono intesi tutti i linguaggi riconoscibili da un automa a stati finiti,

quindi un’espressione regolare è semplicemente una stringa riconosciuta dall’automa.

⋆

0 + 1 1 ⋅ + ⋅ ⋆

: regolare : espressione regolare : non regolare

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Logica Matematica

Descrive con precisione il significato di un enunciato matematico, risolvendo le possibili ambiguità.

Inoltre, permettono di determinare se un quando una dimostrazione è corretta.

La proposizione è un enunciato dichiarativo, che rispetta 2 principi:

• Principio del terso escluso: esso può essere o vero o falso (no altre possibilità);

• Principio di non contraddittorietà: non può essere allo stesso tempo vero e falso.

Calcolo Proposizionale

Chiamata anche logica proposizionale, è utilizzata per operazioni e calcoli di tipo logico.

- Sintassi: rappresenta fatti o enunciati basilari, attraverso i connettivi logici.

= {, , , … . }, ⟨Prop⟩.

Dato l’insieme delle formule prop, è generato dalla categoria

- Formalizzare proposizioni: procedimento di trasformazione di una proposizione.

La proposizione viene estratta dal linguaggio naturale e convertita nel calcolo proposizionale.

- Semantica: si intende il valore che assume, esso dipende dall’interpretazione.

Interpretazione

∶ → {, }

Funzione che assegna un valore di verità ad ogni simbolo proposizionale.

La semantica della formula, è ottenuta per induzione strutturale, dalla valutazione dei connettivi.

Semantica proposizionale

Data un’interpretazione, il valore delle formule proposizionali è dato da una funzione:

⟦⟧ : → {, }

La funzione è applicata per induzione strutturale:

⟦⟧ ⟦⟧

= t = f

1. e

⟦⟧ = () ∈

2. per ogni

⟦(P)⟧ (⟦P⟧ )

= ∈

3. per ogni

⟦¬(Q)⟧ = ¬⟦Q⟧

4. per ogni formula atomica

⟦P ⟦P⟧ ⟦Q⟧

op Q⟧ = ∈ {∧,∨, ⇒, ⇐, ⇔} , ∈

5. per ogni e

Modello, equivalenza e conseguenza logica

▪ ⟦⟧

: = t.

Modello di quando l’interpretazione sul predicato è vera

▪ Logicamente equivalenti: quando due proposizioni hanno lo stesso modello.

Di conseguenza una è il modello dell’altra.

▪

Conseguenza logica: la proposizione è vera per ogni formula dell’insieme

da una formula si riesce ad arrivare all’altra formula

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Tavole di verità .

Permettono di calcola il valore di una formula proposizionale su una interpretazione

La tavola può essere rappresentata anche in modo compatto:

• Scrivo tutto sulla stessa riga, sotto al risultato tengo conto del passo nel quale sono.

• A sx metto tutti i simboli che sto valutando nell’interpretazione (A,B,C)

• A dx metto invece la formula. (

= { → , → , → , … } = ∧ ) ∨ ¬

Ambiguità Sintattica

Nella formula sono presenti più connettivi dello stesso livello, non essendo ambigua la grammatica possono

esserci soltanto due possibilità:

• .

Formula sintatticamente errata, assume valori diversi per la stessa

•

Formula accettata, nonostante l’ambiguità il valore per l’interpretazione è uno solo.

Per evitare questa situazione, si utilizzano sempre le parentesi.

Tautologia

È una formula proposizionale, che è sempre vera per ogni interpretazione.

La formula può essere:

• Insoddisfacibile: è sempre falsa per qualunque interpretazione (contraddizione),

• Soddisfacibile: esiste almeno una interpretazione per la quale è vera

Metodi di verifica

Per vedere sé una formula è una tautologia, esistono principalmente due modi:

▪ Con le tavole di verità, si prova per tutti i valori logici. (costoso)

▪ Dimostrazione per assurdo, genero un’interpretazione che dimostri che non è tautologia.

Dimostrazioni calcolo proposizionale ⇔

La dimostrazione per sostituzione è data da una formula che essa è una tautologia.

La sostituzione consiste in una sequenza di passi giustificati attraverso formule già dimostrate.

, , ,

Date 3 formule il rimpiazzamento è quando P viene ottenuta dalla sostituzione di un’occorrenza di

[/]

R con la formula Q -> ⇔ ⇔

Stabilisce che sé è una tautologia, allora anche P P [R/Q] è una tautologia.

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Verifica tautologia (sostituzione)

Prendiamo come esempio il seguente passo di dimostrazione della formula:

Sistema di dimostrazione (Proof System)

Stabilisce in che modo possono essere costruite le dimostrazioni, date delle premesse.

Mostra, che data una formula, essa è conseguenza logica delle premesse.

,

Un sistema di dimostrazioni è un insieme di regole di inferenza una regola di inferenza è così:

, … ,

1 []

= 0 > 0

Quando la regola è detta assio