logo

Primjeri DFA

Primjer 1:

Dizajnirajte FA s ∑ = {0, 1} prihvaća nizove koji počinju s 1 i završavaju s 0.

Riješenje:

python ili

FA će imati početno stanje q0 iz kojeg će samo rub s ulazom 1 ići u sljedeće stanje.

Primjeri determinističkih konačnih automata

U stanju q1, ako pročitamo 1, bit ćemo u stanju q1, ali ako pročitamo 0 u stanju q1, doći ćemo do stanja q2 koje je konačno stanje. U stanju q2, ako pročitamo ili 0 ili 1, prijeći ćemo u stanje q2 odnosno stanje q1. Imajte na umu da ako unos završava s 0, bit će u konačnom stanju.

Primjer 2:

Dizajnirajte FA s ∑ = {0, 1} prihvaća jedini ulaz 101.

Riješenje:

Primjeri determinističkih konačnih automata

U zadanom rješenju vidimo da će biti prihvaćen samo unos 101. Stoga, za ulaz 101, ne postoji drugi put prikazan za drugi ulaz.

Primjer 3:

Dizajn FA s ∑ = {0, 1} prihvaća parni broj 0 i parni broj 1.

Riješenje:

središnja slika u css-u

Ovaj FA će razmotriti četiri različite faze za unos 0 i unos 1. Faze bi mogle biti:

Primjeri determinističkih konačnih automata

Ovdje je q0 početno stanje i također konačno stanje. Pažljivo primijetite da se održava simetrija 0 i 1. Svakom stanju možemo pridružiti značenja kao:

q0: stanje parnog broja 0 i parnog broja 1.
q1: stanje neparnog broja 0 i parnog broja 1.
q2: stanje neparnog broja 0 i neparnog broja 1.
q3: stanje parnog broja 0 i neparnog broja 1.

Primjer 4:

Dizajn FA s ∑ = {0, 1} prihvaća skup svih nizova s ​​tri uzastopne nule.

Riješenje:

Nizovi koji će se generirati za ove određene jezike su 000, 0001, 1000, 10001, .... u kojima se 0 uvijek pojavljuje u skupini od 3. Grafikon prijelaza je sljedeći:

Primjeri determinističkih konačnih automata

Imajte na umu da se niz trostrukih nula održava kako bi se postiglo konačno stanje.

Primjer 5:

Dizajnirajte DFA L(M) = {w | w ε {0, 1}*} i W je niz koji ne sadrži uzastopne 1.

Riješenje:

primjeri python programa

Kada se dogode tri uzastopne 1, DFA će biti:

Primjeri determinističkih konačnih automata

Ovdje su prihvatljive dvije uzastopne 1 ili jedna 1

Primjeri determinističkih konačnih automata

Faze q0, q1, q2 su završna stanja. DFA će generirati nizove koji ne sadrže uzastopne 1 kao što su 10, 110, 101,..... itd.

Primjer 6:

Dizajnirajte FA s ∑ = {0, 1} prihvaća nizove s parnim brojem 0 iza kojih slijedi jedna 1.

Riješenje:

DFA se može prikazati tranzicijskim dijagramom kao:

Primjeri determinističkih konačnih automata