Finite State Machine numero dispari di bc alla fine

Question

Finite State Machine numero dispari di bc alla fine

#1 da (3 voti)

-2

Ho avuto questa domanda in un test scolastico:

Design a non-deterministic FSM that receives all words over {a,b,c} that:

Start with cc.

Contain at least 1 ab or aca.

Ends with an odd number of (bc).

L'FSM che ho costruito era sbagliato. Tuttavia, quando ho chiesto all'insegnante un FSM che funzioni, lei mi ha dato questo: (ignora il testo).

Da come la vedo io, questo FSM non funziona, perché ad esempio la parola ccabcbc dalla rotta

q0->q1->q2->q3->q4->q4->q6->q7

Ma lei dice solo che l'FSM funziona e che non capisco come funzioni un FSM non deterministico.

Quindi, sbaglio o è lei? se ho torto, perché la via che ho dato non è valida? E se ho ragione, sarebbe bello se qualcuno potesse inviare un FSM che funzioni, perché stavo lottando con questo anche a casa.

Grazie in anticipo, e mi dispiace per l'uso improprio dei termini, imparo l'argomento in una lingua diversa.

finite-state-machine

posta hrsidkpi 12.12.2017 - 08:16

fonte

1 risposta

Leggi altre domande sui tag finite-state-machine

Come determinare rapidamente il comportamento di un codice sorgente complicato? [duplicare] Usare git su un progetto con aree diverse

score 3 · Accepted Answer

Il tuo professore ha torto. L'attività "accetta un numero dispari di bc alla fine" può solo significare "accetta solo un numero dispari (e non un numero pari) di bc , altrimenti non ci sarebbe alcun punto anche dichiarando la condizione - ogni numero pari di ripetizioni termina anche con un numero dispari di ripetizioni se contate dalla posizione giusta.

Quindi come si scrive un automa che accetta solo un numero dispari di bc alla fine? Il trucco è assicurarsi che le transizioni immediatamente prima del ciclo finale non accettino bc . Ad esempio, puoi creare sette percorsi diversi per tutte le combinazioni di altri due simboli e assicurarti che lo stato finale sia raggiungibile solo tramite loro.

(Questo sembra costoso, ed è vero. Le condizioni di negazione nelle normali lingue sono spesso sorprendentemente complicate. Forse hai imparato che le lingue regolari sono chiuse in negazione, ed è vero - è sempre possibile creare una macchina che accetti il contrario di una lingua, ma la teoria non dice che sarà a buon mercato, e infatti spesso non lo è.)