Appunti Fondamenti, Linguaggi e Traduttori (FLT)

Fondamenti, linguaggi e traduttori

Alfabeto

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

Linguaggio = insieme di stringhe costruite su un alfabeto

Un linguaggio formale non deve essere ambiguo

• l1 = ab = | l1 | = 2
• l2 = aab = | l2 | = 3
• l2 = a = | l2 | = 1
• l2 = ε = | l2 | = 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 linguage

L1 L2 = {x y x ∈ L1, y ∈ L2}

• Φ L = Φ e L1 = Φ
• L Φ = Φ e | ε |

Potenza

• a^0 = ε se n = 0
• a^ε = se n ≠ 0

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

L^0 = {ε}

Operatore di Kleene

a* = U a^n

L* = U L^n

Operatore +

a+ = a a* = aa*

L+ = U L^n

Complemento

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

Espressioni regolari

Dato un alfabeto sono espressioni regolari:

• Φ
• ε
• ∀ a ∈ Σ (a è uno da simboli dell’alfabeto)

Def Date e₁, e₂ espressioni regolari:

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

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

ex 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 parentet anche 0 volte, potrei ottenere un segno seguito

dal nulla = errore = scambio* → con +

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

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

Ho un problema non riesco a generare lo etero da solo.

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

Derivazione e₁ ⟹ e₂ se e₂ e sottoinsieme di e₁.

• Regole: e₁ e e₂ U e_n ⟹ e₁
• e* ⟹ e^n 0 ≤ n

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

Fondamenti, linguaggi e traduttori

Alfabeto

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

L = {ε} |L| = 1

|| = cardinalità

Linguaggio

• 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

L₁L₂ = {x₁x₂ | x₁ ∈ L₁, x₂ ∈ L₂}

∅ = {x} ∅

Potenza

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

L = L^Σ ∩ Σ^*

L' = L^U - L

Espressioni regolari

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

Def

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₂

• Σ = {+, -, 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₁.