Appunti Fondamenti, Linguaggi e Traduttori (FLT)

Fondamenti, linguaggi e traduttori

Alfabeto e cardinalità

Alfabeto Σ = {a, b} |Σ| = numero di simboli |Σ| = cardinalità

Linguaggio e struttura

Linguaggio = insieme di stringhe costruite su un alfabeto

Un linguaggio formale non deve essere ambiguo

l₁ = ab = | l₁ | = 2

l₂ = aab = | l₂ | = 3

l₂ = a = | l₂ | = 1

l₂ = ε = | l₂ | = 0

Stringa vuota ε |ε| = 0

Linguaggio vuoto ∅ |∅| = 0

L = { ε } | L | = 1 caso particolare (linguaggio formato da solo ε)

Concatenamento

x = aab y = bbb x y = aabbba

Concatenamento di linguaggi L₁ L₂ = {x y | x ∈ L₁, y ∈ L₂}

Φ L = Φ e L₁ = Φ

L Φ = Φ e | ε |

Potenza

a⁰ = ε se n = 0

a^ε = se n ≠ 0

Lⁿ = { L^(n−1) L se n ≠ 0

L⁰ = {ε}

Operatore di Kleene

a* = U aⁿ

L* = U Lⁿ

Operatore +

a⁺ = a a* = aa*

L⁺ = U Lⁿ

Complemento

L = L U L = Σ* = L = Σ

Espressioni regolari

Dato un alfabeto sono espressioni regolari: Φε∀ a ∈ Σ (a è uno dei simboli dell’alfabeto)

Definizione: Date e₁, e₂ espressioni regolari:

• se e₁ e e₂, allora e₁
• se e₁ e e₂, allora e₁ e e₂

Espressione regolare per numeri interi

Σ = {+ , - , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

Scrivere l'espressione regolare che permette di scrivere un numero intero con segno o senza (con la zero).

Σ = {+ , - , ε, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

→ (+ U - U ε) (0 U 1 U 2 U 3 U . . . U 9)*

Ho male posizionato potenze, e parente la seconda parentesi anche 0 volte, potrei ottenere un segno seguito dal nulla = errore = scambio * → con +

Esempio: sarebbe possibile generare un numero come +00001 (biogotti)

→ (+ U - U ε) ((1 U . . . U 9)(0 U 1 U . . . U 9)*) U 0

Problemi e soluzioni

Ho un problema: non riesco a generare lo zero da solo.

→ ((+ U - U ε) ((1 U . . . 9)((0 U 1 U . . . U 9)*) U 0

Derivazione

e₁ → e₂, se e₂ è sottoinsieme di e₁.

Regole: e₁ e e₂ U e_n → e₁

e* → eⁿ 0 ≤ n

Derivazione immediata: e₁ → e₂ se A ⊆ B ed e₂ → α β ed e₂ → α B, allora A → ε

Alfabeto aggiuntivo

Σ = {a, b, 1} |Σ| = numero di simboli

L = {ε} |L| = 1

|| = cardinalità

Linguaggio vuoto e concatenamento

L'insieme di stringhe costruite su un alfabeto ε ∈ L

l₁ = b | l₁ = L {1}

l₂ = a | l₁ = L {2}

L = {ε, l₁, l₂} |L| = 1001

caso particolare (linguaggio formato da sola ε)

Stringa vuota: ε = l_i⁰

Linguaggio vuoto: ∅ = L ∈() |L| = 0

Concatenamento: x = aaε, y = bbb, z = aaabbb

Concatenamento di linguaggi e potenza

Concatenamento di linguaggi: L₁L₂ = {x₁x₂ | x₁ ∈ L₁, x₂ ∈ L₂}

∅ = {x} ∅

Potenza e operatori

a₀ = ε, se n = 0

a^-n = ∅, se n ≠ 0

Lⁿ = {l₁l₂ ... l_n | l_i ∈ L }, se n ≠ 0

Operatore di Kleene: a^* = ⋃_{i = 0}ⁿ Lⁱ

Operatore +: a⁺ = Lⁱ

Complemento e espressioni regolari

Complemento: L = L^Σ ∩ Σ^*

L' = L^U - L

Espressioni regolari da un alfabeto sono espressioni regolari: ∅ε∀ a ∈ Σ (a è uno dei simboli dell'alfabeto)

Ulteriori definizioni

Definizione: Date e₁, e₂ espressioni regolari:

• se e₁ e e₂, allora e₁ e₂
• se e₁, e₂ sono e, allora e₁ e₂
• se e₁ e e₂ sono e_i allora e₁ ∪ e₂

Espressione regolare per numeri interi

Σ = {+, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

Scrivere l'espressione regolare che permette di scrivere un numero intero con segno o senza (con lo zero).

Σ = {+, -, ε, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0} → { (+ ∪ - ∪ ε) (0 ∪ 1 ∪ 2 ∪ 3 ∪ 4 ∪ 8 ∪ 9) → * Ho ∅ problema, ε potrebbe ∅, e scambiare * con +.

ε che genera il minimo con ε solo.

Ho ∅ per generare lo zero da solo.

→ ((+ ∪ - ∪ ε) (0 ∪ 1 ∪ 2 ∪ 3 ∪ 4 ∪ 5 ∪ 9 ∪ 9 ∪ 0 ∪ 1 ∪ 9)

Derivazione

e₁ → e₂, se e₂ è sottoinsieme di e₁.