Esempio 1:
Progettare una NFA per la tabella di transizione come indicato di seguito:
| Stato attuale | 0 | 1 |
|---|---|---|
| →q0 | q0, q1 | q0, q2 |
| q1 | q3 | e |
| q2 | q2, q3 | q3 |
| →q3 | q3 | q3 |
Soluzione:
Il diagramma di transizione può essere disegnato utilizzando la funzione di mappatura come indicato nella tabella.
Qui,
δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3} Esempio 2:
Progettare un NFA con ∑ = {0, 1} accetta tutte le stringhe che terminano con 01.
Soluzione:
Quindi, NFA sarebbe:
Esempio 3:
Progetta un NFA con ∑ = {0, 1} in cui il doppio '1' è seguito dal doppio '0'.
Soluzione:
La FA con doppio 1 è la seguente:
prepararsi per il test mockito
Dovrebbe essere immediatamente seguito dal doppio 0.
Poi,
Ora, prima del doppio 1, può esserci qualsiasi stringa di 0 e 1. Allo stesso modo, dopo il doppio 0, può esserci qualsiasi stringa di 0 e 1.
Quindi la NFA diventa:
Consideriamo ora la stringa 01100011
q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4
Esempio 4:
Progetta un NFA in cui tutte le stringhe contengono una sottostringa 1110.
Soluzione:
Il linguaggio è costituito da tutta la stringa contenente la sottostringa 1010. Il diagramma di transizione parziale può essere:
Ora, poiché 1010 potrebbe essere la sottostringa. Quindi aggiungeremo gli input 0 e 1 in modo che la sottostringa 1010 del linguaggio possa essere mantenuta. Quindi la NFA diventa:
La tabella di transizione per il diagramma di transizione sopra può essere fornita di seguito:
| Stato attuale | 0 | 1 |
|---|---|---|
| →q1 | q1 | q1, q2 |
| q2 | q3 | |
| q3 | q4 | |
| q4 | q5 | *q5 | q5 | q5 |
Considera una stringa 111010,
δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00)
Rimasto bloccato! Poiché non esiste un percorso da q2 per il simbolo di input 0, possiamo elaborare la stringa 111010 in un altro modo.
δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε)
Poiché lo stato q5 è lo stato di accettazione. Otteniamo la scansione completa e raggiungiamo lo stato finale.
Esempio 5:
Progettare un NFA con ∑ = {0, 1} accetta tutte le stringhe in cui il terzo simbolo dall'estremità destra è sempre 0.
convertire l'array di byte in stringa
Soluzione:
Quindi otteniamo il terzo simbolo dall'estremità destra sempre come '0'. La NFA può essere:
L'immagine sopra è un NFA perché nello stato q0 con input 0, possiamo andare allo stato q0 o q1.