Appunti quaderno di Automi e linguaggi

Stato d'accettazione

Stato d'accettazione: particolare stato di una macchina che ha il compito di indicare la condizione di verità. Se alla fine dell'esecuzione capito nello stato di accettazione allora la condizione che sto verificando è vera, altrimenti falsa.

Esempio

È possibile costruire una macchina con memoria di 2 bit che verifichi se una stringa di bit rappresentanti un numero in base 2 costituisca un multiplo di 3.

Memoria di 2 bit ⇒ 4 stati.

Una prima ipotesi: questo primo automa funziona a patto che la stringa in ingresso non sia vuota. In tal caso l'esecuzione parte dallo stato iniziale q₀ e lì ritorna.

Esempio corretto

Stato d'accettazione: particolare stato di una macchina che ha il compito di indicare la condizione di verità. Se alla fine dell'esecuzione capito nello stato di accettazione allora la condizione che sto verificando è vera, altrimenti falsa.

È possibile costruire una macchina con memoria da 2 bit che verifichi se una stringa di bit rappresentanti un numero in base 2 costituisca un multiplo di 3.

Memoria di 2 bit ⇒ 4 stati.

Una prima ipotesi: questo primo automa funziona a patto che la stringa in ingresso non sia vuota. In tal caso l'esecuzione parte dallo stato iniziale q₀ e lì ritorna.

Lezione 2

Linguaggi

Alphabet Σ: finite set of "symbols", not empty (Σ ≠ ∅).

String over Σ: finite sequence of symbols in Σ - es: Σ = {a, b, c ... z} String ➔ "aabcada".

Σ* = { "a", "b", "aa" ... }

Σ* = { all string over Σ }

Length of a string: # of symbols.

Null string ε: string with no symbols ε_{length = 1}.

Substring: una stringa è una sottostringa di un'altra se i caratteri che compongono la sottostringa compaiono nello stesso ordine nella stringa di partenza.

Concatenation: la concatenazione di due stringhe crea una nuova stringa costituita da tutti i caratteri della prima stringa ordinati consecutivi seguiti dai caratteri della 2^o stringa ordinati.

Lessicographical order: alfa ⬍ beta, gli elementi dell'alfabeto sono ordinati quindi si può definire un ordine di precedenza.

String order (shortest order): una stringa più corta precede sempre una più lunga, a parità di lunghezza si utilizza ordine lessicografico per stabilire l'ordinamento alfa ⬍ beta alfa ⬎ bit.

Language over Σ

Language over Σ

Subset of string over Σ L ⊆ Σ* - es: Σ = {0, 1, 2} Σ* = {ε, 0, 1, 00, 01 ... }.

L = { w ∈ Σ* | w encodes in binary a number divisible by 3 }.

L = {0, 11, 110, 1001 ...} ε ∉ L 1 ∉ L.

"Un linguaggio rappresenta le istanze che soddisfano un certo quesito" - nel nostro esempio: m ∈ N ➔ (01101)₂ = "01101" ∈ L ⟨ Sì ⟩ ⟨ No ⟩

"Un linguaggio può modellare un problema decisionale".

Possiamo codificare sulla macchina delle istruzioni che portano da uno stato all'altro sulla base della lettura dei simboli in una certa stringa.

La macchina transita da uno stato all'altro stabilendo che se l'ultimo simbolo letto della stringa ti porta in Q_f allora la macchina accetta la stringa (fa parte del linguaggio).

Finite state automata (DFA)

Finite State Automata (DFA)

M = (Q, Σ, δ, q₀, F)

La macchina (autom)

• Q: "States"
• Σ: "Alphabet"
• δ: Q x Σ → Q "Transition Function"

È una funzione quindi: per ogni coppia esiste un q_i ⟼ (q_i, σ) ⟼ q_i'

Stato che la macchina ha prima di leggere il primo simbolo.