|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-AutomiStatiFiniti History
Hide minor edits - Show changes to output
Changed line 40 from:
*''q'_0_''' è lo stato finale to:
*''q'_0_''' è lo stato iniziale
Changed line 29 from:
*''δ''(''r'_i_''', ''w'_i+1_''') = ''r'_i_''' per ''i'' = 0, 1, ..., ''n''-1 → la macchina passa da uno stato all'altro in accordo alla funzione di transizione to:
*''δ''(''r'_i_''', ''w'_i+1_''') = ''r'_i+1_''' per ''i'' = 0, 1, ..., ''n''-1 → la macchina passa da uno stato all'altro in accordo alla funzione di transizione Changed line 52 from:
Siano ''A'' e ''B'' due linguaggi, definiamo le operazioni di '''unione''', '''concatenzaione''' e '''star''' come segue: to:
Siano ''A'' e ''B'' due linguaggi, definiamo le operazioni di '''unione''', '''concatenazione''' e '''star''' come segue:
Changed line 42 from:
to:
Changed line 58 from:
!!Chiusura di un linguaggio to:
!!!Chiusura di un linguaggio Added lines 61-79:
!!!Proprietà dei linguaggi regolari
È possibile dimostrare che i linguaggi regolari sono chiusi rispetto all'operazione di unione, quindi l'unione di due linguaggi regolari è un altro linguaggio regolare:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Siano ''A'_1_''' e ''A'_2_''' due linguaggi regolari e ''M'_1_''' e ''M'_2_''' rispettivamente gli automi a stati finiti che li riconoscono.
Vogliamo costruire l'automa ''M'' che riconosce il linguaggio ''A'_1_''' ∪ ''A'_2_'''.
%center%''M'_1_' = (Q'_1_', Σ, δ'_1_', q'_1_', F'_1_')''\\
''M'_2_' = (Q'_2_', Σ, δ'_2_', q'_2_', F'_2_')''\\
''M = (Q, Σ, δ, q, F)''
''Q = Q'_1_' × Q'_2_' = {(r'_1_',r'_2_') | r'_1_' ∈ Q'_1_' ∧ r'_2_' ∈ Q'_2_'}''\\
''δ : Q × Σ → Q''\\
''δ((r'_1_', r'_2_'), a) = (δ'_1_'(r'_1_', a), δ'_2_'(r'_2_', a)), (r'_1_', r'_2_') ∈ Q ∧ a ∈ Σ''\\
''q = (q'_1_', q'_2_')''\\
''F = {(r'_1_', r'_2_') | r'_1_' ∈ F'_1_' ∧ r'_2_' ∈ F'_2_'}''
Abbiamo dimostrato per costruzione che esiste l'automa a stati finiti riconoscitore del linguaggio unione, che è quindi un linguaggio regolare.
>><<
Added lines 23-24:
I linguaggi riconosciuti dagli automi a stati finiti si chiamano '''linguaggi regolari'''. Un linguaggio è regolare se esiste un automa a stati finiti che lo riconosce. Changed line 50 from:
!!!Operazioni sui linguaggi
to:
!!Operazioni sui linguaggi Added lines 57-60:
!!Chiusura di un linguaggio
Una collezione di oggetti è '''chiusa''' rispetto ad una determinata operazione se applicando l'operazione ai membri della collezione si ottiene un oggetto appartenente ancora alla collezione.
Facendo riferimento ai linguaggi possiamo dire che una classe di linguaggi è chiusa rispetto ad un'operazione se applicando l'operazione ai linguaggi della classe otteniamo ancora un linguaggio della stessa classe.
Added lines 47-54:
!!!Operazioni sui linguaggi
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Siano ''A'' e ''B'' due linguaggi, definiamo le operazioni di '''unione''', '''concatenzaione''' e '''star''' come segue:
*'''unione''': ''A'' ∪ ''B'' = {''x'' | ''x'' ∈ ''A'' ∨ ''x'' ∈ ''B''}, ovvero l'insieme delle stringhe che appartengono a ad almeno uno dei due linguaggi
*'''concatenazione''': ''A'' • ''B'' = {''xy'' | ''x'' ∈ ''A'' ∧ ''y'' ∈ ''B''}, ovvero l'insieme delle stringhe formate da una stringa di ''A'' seguita da una di ''B''
*'''star''': '''A''''^∗^' = {''x'_1_'x'_2_'...x'_k_''' | ''k'' ≥ 0 ∧ ''x'_i_''' ∈ ''A''}, l'insieme di tutte le concatenazioni delle stringhe di ''A''
>><<
Changed lines 21-23 from:
Un esempio di automa a stati finiti è lche riconosce le stringhe di bit in cui il numero di 1 è dispari:
to:
Se ''A'' è l'insieme delle stringhe accettate dall'automa ''M'' allora ''A'' è il linguaggio della macchina ''M'' (''L(M) = A'') e si dice che ''M'' riconosce ''A''.
Ma cosa vuol dire accettare una stringa? Significa che partendo dallo stato iniziale, l'automa deve terminare la sua computazione in uno stato d'accettazione. Più formalmente:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Dato ''M'' = (''Q'', ''Σ'', ''δ'', ''q'_0_''', ''F'') e una stringa d'ingresso ''w'' = ''w'_1_'w'_2_'w'_3_'...w'_n_''' dove ogni ''w'_i_' ∈ Σ'', si dice che ''M'' accetta ''w'' se esiste una sequenza di stati ''r'_0_', r'_1_', ..., r'_n_''' in ''Q'' che rispetti le seguenti 3 condizioni:
*''r'_0_' = q'_0_''' → la macchina parte dallo stato iniziale
*''δ''(''r'_i_''', ''w'_i+1_''') = ''r'_i_''' per ''i'' = 0, 1, ..., ''n''-1 → la macchina passa da uno stato all'altro in accordo alla funzione di transizione
*''r'_n_' ∈ F'' → la macchina termina in uno stato accettante
>><<
Un esempio di automa a stati finiti è la macchina ''M'' che riconosce il linguaggio ''A'' = {''w'' | ''w'' è una stringa con un numero dispari di 1}: Changed line 42 from:
|| || '''0''' || '''1''' || to:
|| || '''0''' || '''1''' ||
Changed lines 24-25 from:
%center% ''M'' = (''Q'', ''Σ'',''δ'',''q'_0_''',''F'') to:
%center% ''M'' = (''Q'', ''Σ'', ''δ'', ''q'_0_''', ''F'') Added line 36:
Changed line 36 from:
to:
%center%Attach:IT-L1-DFS-1.png
Changed line 14 from:
Un automa a stati finiti è una 5-tupla (''Q'', ''Σ'',''δ'',''q'_0_''',''F'') dove: to:
Un automa a stati finiti è una 5-tupla (''Q'', ''Σ'', ''δ'', ''q'_0_''', ''F'') dove: Changed lines 18-19 from:
*''q'_0_'∈Q'' è lo stato iniziale dell'automa
*''F⊆Q'' è l'insieme degli stati accettanti to:
*''q'_0_' ∈ Q'' è lo stato iniziale dell'automa
*''F ⊆ Q'' è l'insieme degli stati accettanti Added lines 21-36:
Un esempio di automa a stati finiti è l'automa ''M'' che riconosce le stringhe di bit in cui il numero di 1 è dispari:
%center% ''M'' = (''Q'', ''Σ'',''δ'',''q'_0_''',''F'')
dove
*''Q'' = {''q'_0_''', ''q'_1_'''}
*''Σ'' = {0, 1}
*''q'_0_''' è lo stato finale
*''F'' = {''q'_1_'''}
*''δ'' =
||border="1" bordercolordark="black" bordercolorlight="black" style="border-collapse:collapse" cellpadding="5"
|| || '''0''' || '''1''' ||
||'''''q'_0_''''''||''q'_0_'''||''q'_1_'''||
||'''''q'_1_''''''||''q'_1_'''||''q'_0_'''
Attach:IT-L1-DFS-1.png
Changed line 12 from:
Può essere definito fomrlamente in questo modo: to:
Può essere definito formalmente in questo modo:
Added lines 1-23:
(:title Informatica Teorica - Automi a stati finiti:)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Automi a stati finiti ::'''
%center% %sottotitolo% Appunti del 3 Marzo
!!Automa a stati finiti
L'automa a stati finiti (o macchina a stati finiti) è il modello computazionale più semplice ma con una quantità limitata di memoria.
Può essere definito fomrlamente in questo modo:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un automa a stati finiti è una 5-tupla (''Q'', ''Σ'',''δ'',''q'_0_''',''F'') dove:
*''Q'' è l'insieme finito degli stati dell'automa
*''Σ'' è un insieme finito di simboli chiamato alfabeto
*''δ: Q × Σ → Q'' è la funzione di transizione che dato uno stato e un simbolo in ingresso indica qual'è lo stato futuro dell'automa
*''q'_0_'∈Q'' è lo stato iniziale dell'automa
*''F⊆Q'' è l'insieme degli stati accettanti
>><<
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
