Appunti quaderno di Automi e linguaggi

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 q4 e li rimane

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.

Esempio:

È 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 li ritorna.

Esempio corretto:

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° 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 parita di lunghezza si utilizza ordine lessicografico per stabilire l'ordinamento

alfa ⬍ beta alfa ⬎ bit

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)

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