Appunti Fondamenti, Linguaggi e Traduttori (FLT)

Fondamenti linguaggi e traduttori

Alfabeto

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

Linguaggio: l'insieme di stringhe costruite su un alfabeto

Un linguaggio formale non deve essere ambiguo

Stringa vuota

ε: |ε| = 0

Linguaggio vuoto

L = {ε} |L| = 1

Caso particolare (linguaggi formati da solo ε)

Concatenamento

X Y = aaabbb Y = bbb X Y = aaabbb

Concatenamento di linguaggi

• L₁ L₂ = {x y | x ∈ L₁, y ∈ L₂}
• Σ L = L L Σ = L
• ∅L = L∅ = ∅

Potenze

• aⁿ = {aⁿ} se n ≠ 0
• {ε} se n = 0

Operatore di Kleene

L* = ⋃_i=0^∞Lⁱ

Operatore +

Concatenamento

a⁺ = aⁿ con n ≠ 0

Complemento

• L &supl; Σ* L = Σ* - L

Espressioni regolari

Dato un alfabeto sono espressioni regolari:

• ∅
• ε
• ∀ a ∈ Σ (a è uno dei simboli dell'alfabeto)

Def: Date e₁, e₂ espressioni regolari:

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

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

L = Σ ∅ + -

Ex

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

• = Σ{+, - ,0,1,2,3,4,5,6,7,8,9,0}
• (+ - ∪ ∅)(0 ∪ 1 ∪ 2 ∪ 3 ∪...9)*
• Ho un problema potendo generare le seconde parenzeω anche o vare, potrei ottenere un segno seguitodallo nulla — errore — scambio `* con +`
• Ho un problema posso generare numeri come 0+000 • (bloccato) => (+ -  
• ∃ {(∪, 0, 1, ∪, 2, 3, ∪, 9)}(0 ∪ 1 & u;
• Mo un problema — non riesca generare lo letto πla sola
• (+ ∪ - ∪ ∅)(2,3;(0,0 0,1,2,9)(0 ∪ Σ,9)* ∪ 0

Derivazione

• e₁ → e₂ se e₂ è sottinsieme di e₁
• Regole : e₁, e₂, ∪ V ∃
• e₂ → n, 0 ≤ n

Derivazione immediata

e₁ → e₂ se dato e₁, a β ed e₂ α n β allora δ → γ

1. (a∪b)(a∪b)* ⊨

• (a∪b) (a∪bb) L
• (a∪b) (a∪bb) a*
• (a∪b) (a∪bb) a
• (a∪b) (a∪bb) aa
• ba (a∪bb)a
• ba (a∪bb)a

Regole concatenamento linguaggi ed e.c.

• L(e₁e₂) = L(e₁, e₂)
• L(e)∪L(e₂)
• L(e₁, e₂) = L(e, e₂)

Idem per intersezione, differenza, complemento.

Errori:

• aⁿbⁿ n≥0 (il numero di a è uguale al numero b) (non è descrivibile tramite e.c.)
• aⁿ bʳ (prende anche case in più)

Palindromi

∑:={a,b} ⟹ a₂a₂

abba

a b ba NO (Fa la ricerca di un tag = simbolo che non esistente)

∫∫ deve avere un numero pari di simboli

Regole grammaticali

• Se ho un dato simbolo, lo posso sostituire con altri simboli
• PAL ⟹ a PAL a
• PAL ⟹ b PAL b
• PAL ⟹ a
• PAL ⟹ b
• Non genera la stringa vuota

Grammatica

= quadrupla ⟨V, Σ, P, S⟩ dove:

• V = simboli non terminali (maiuscoli, indica ciò che parola non è ancora terminato)
• Σ = Alfabeto, simbolo terminali
• P = insieme di tutte le regole grammaticali (coppie di produzione)
• S = assieme, ovvero da dove parte

es:

• P: F ⟹ A | a A | a
• B ⟹ h A
• V: {a, B}
• Σ: {a, b}

(A ⟹ a A | a = a A = a)

• S = a b A
• Se Σ = B, allora B ⟹ b F ⟹ ba
• Se Σ = B, allora non genera nulla se non a

Qualunque linguaggio composto da un numero finito di parole è regolare

L(G)={x∈Σ* : S⟹* x}

er di grammatica

• V :={S, A, B} ∑ :={a, b}
• S ⟹ A a | S (da S arrivo a S)
• A ⟹ S (da A vado a S) S⟹* S
• A ⟹ b S (ovvero : non avere B nella grammatica e denomina specifici simboli di spazio)

Grammatica ridotta

• ∀ A Є V ∃ α β ≠ A
• ∀ A Є V ∀ α Σ* ∃ β
• ∀ A Є V S* ⟹ α β ⟹ dove α, β ∈ (V U Σ)*

Es grammatica che descrive le operazioni aritmetiche * e + (grammatici ridotte)

E ➝ E + T | T

T ➝ T * F | F

F ➝ (E) | n (n numero generale: a)

Macchina di Turing

Modello matematico (astratto) proposto da Alan Turing che costituisce l'anticipatore formale di un computer moderno.

• Controller
• Nastro infinito
• 0, 1, blank (nello stato vuoto)

Funzione del nastro:

CPU dove sta il programma

• Descritta tramite funzioni matematiche
• Tipo: [N] ma devo fare in memoria del passato

funzione di transizione stato

dato da inserire

Linguaggi: Context Sensitive + regole

L = {aⁿbⁿcⁿ, n ≥ 1}, L = {x y c^y | x ∈ Σ \ {c}|}

S → X c

fine stringa per 'cⁱ'

X a X → A I b X B

X B → X B

• X B → X A'
• A → aa
• B' → b
• A → ab
• A' → a A'
• C c
• B' B → B B C B' B → B C B
• B → b
• B' → B' B B B B' → B B' B' B B B B B B' B' B
• S → a S B c

Linguaggi Context Free

L = {aⁿbⁿ⁺¹ c^d m} n ≥ 1, m ≥ 2

Bilanciamento

• S → T c d
• D → d|d b
• T → a T b|abb

S → a S c|a|c

A →

S → AB d

A → a A b|a (X n: minimu d = ae b = 0)

• C → c C|
• B → b C|
• B → b B|

Bilanciamenti in sequenza (sempre context free)

aⁿn^m+2 = (c u d)^k a^c m b^d k n k z

N K

b b d a a

• S → t d
• N → B H e
• N (N senza |a e k, N|a e k|a|dc la|Ia)

* = contiene stati finali

ecc...

Automa a stati finito

Espressioni Regolari

Grammatiche Linear dx

Q = V

q₀ = S

A → bB

A → aB

A → a

A → ε

V = {S, A, B}

F = ∠ A, B '

A → ε

B → ε

S → 0A

A → 1S

A → 0A A → 1B

Esercizi

E1: aⁿbⁿ n > 0

aabb

• PUSH X
• a PUSH X
• b POP
• b POP

• (q₀, a, z₀) → (q₂, Xz₀)
• (q₂, a, Z) → (q₂, XX)
• (q₂, b, X) → (q₂, ε)
• (q₂, ε, z₀) → (q₃, z₀)

E2: aaab

• S
• a
• S
• a
• S
• A
• a
• A
• a
• b
• A
• b

Esercizi

E1: (a U b)ⁿc_a c_b n > 0

• S → X S aa | caa
• X → a | b

E2: L = a²b^md^maⁿa^n-1 m > 0, n > 1

• S → a S a | a B a
• B → b b b | D
• D → d d | ε