Esempio 1:
Progettare una FA con ∑ = {0, 1} accetta quelle stringhe che iniziano con 1 e finiscono con 0.
Soluzione:
L'FA avrà uno stato iniziale q0 dal quale solo il fronte con ingresso 1 passerà allo stato successivo.
Nello stato q1, se leggiamo 1, saremo nello stato q1, ma se leggiamo 0 nello stato q1, arriveremo allo stato q2 che è lo stato finale. Nello stato q2, se leggiamo 0 o 1, andremo rispettivamente allo stato q2 o allo stato q1. Tieni presente che se l'input termina con 0, sarà nello stato finale.
Esempio 2:
Progettare una FA con ∑ = {0, 1} accetta l'unico input 101.
Soluzione:
Nella soluzione data, possiamo vedere che verrà accettato solo l'input 101. Pertanto, per l'ingresso 101, non è mostrato alcun altro percorso per l'altro ingresso.
Esempio 3:
Il progetto FA con ∑ = {0, 1} accetta un numero pari di 0 e un numero pari di 1.
Soluzione:
Questo FA prenderà in considerazione quattro diverse fasi per l'ingresso 0 e l'ingresso 1. Le fasi potrebbero essere:
Qui q0 è uno stato iniziale e anche lo stato finale. Nota attentamente che viene mantenuta una simmetria di 0 e 1. Possiamo associare significati ad ogni stato come:
q0: stato del numero pari di 0 e del numero pari di 1.
q1: stato del numero dispari di 0 e del numero pari di 1.
q2: stato del numero dispari di 0 e del numero dispari di 1.
q3: stato del numero pari di 0 e del numero dispari di 1.
Esempio 4:
Il progetto FA con ∑ = {0, 1} accetta l'insieme di tutte le stringhe con tre 0 consecutivi.
Soluzione:
Le stringhe che verranno generate per queste particolari lingue sono 000, 0001, 1000, 10001, .... in cui 0 appare sempre in un gruppo di 3. Il grafico della transizione è il seguente:
Si noti che la sequenza di tripli zeri viene mantenuta per raggiungere lo stato finale.
Esempio 5:
Progetta un DFA L(M) = {w | w ε {0, 1}*} e W è una stringa che non contiene 1 consecutivi.
Soluzione:
Quando si verificano tre 1 consecutivi, il DFA sarà:
Qui sono accettabili due 1 consecutivi o un singolo 1, quindi
Gli stadi q0, q1, q2 sono gli stati finali. Il DFA genererà le stringhe che non contengono 1 consecutivi come 10, 110, 101,..... ecc.
Esempio 6:
Progetta una FA con ∑ = {0, 1} accetta le stringhe con un numero pari di 0 seguite da un singolo 1.
Soluzione:
Il DFA può essere rappresentato da un diagramma di transizione come:
