1 pavyzdys:
Sukurkite FA su ∑ = {0, 1} priima tas eilutes, kurios prasideda 1 ir baigiasi 0.
Sprendimas:
FA turės pradžios būseną q0, iš kurios tik kraštas su įėjimu 1 pereis į kitą būseną.
Būsenoje q1, jei skaitysime 1, būsime q1 būsenoje, bet jei būsenoje q1 skaitysime 0, pasieksime būseną q2, kuri yra galutinė būsena. Būsenoje q2, jei skaitome 0 arba 1, pereisime atitinkamai į q2 būseną arba q1 būseną. Atminkite, kad jei įvestis baigiasi 0, ji bus galutinės būsenos.
2 pavyzdys:
Sukurkite FA su ∑ = {0, 1} priima vienintelę įvestį 101.
kaip rūšiuoti masyvų sąrašą java
Sprendimas:
Pateiktame sprendime matome, kad bus priimta tik įvestis 101. Vadinasi, 101 įėjimui nėra parodytas kitas kelias.
3 pavyzdys:
Projektas FA su ∑ = {0, 1} priima lyginį skaičių 0 ir lyginį skaičių 1.
Sprendimas:
Šiame FA bus nagrinėjami keturi skirtingi 0 ir 1 įvesties etapai. Etapai gali būti:
Čia q0 yra pradžios būsena ir galutinė būsena. Atidžiai atkreipkite dėmesį, kad išlaikoma 0 ir 1 simetrija. Kiekvienai būsenai galime susieti reikšmes taip:
q0: lyginio skaičiaus 0 ir lyginio skaičiaus 1 būsena.
q1: nelyginio skaičiaus 0 ir lyginio skaičiaus 1 būsena.
q2: nelyginio skaičiaus 0 būsena ir nelyginio skaičiaus 1 būsena.
q3: lyginio skaičiaus 0 ir nelyginio skaičiaus 1 būsena.
4 pavyzdys:
Dizainas FA su ∑ = {0, 1} priima visų eilučių rinkinį su trimis iš eilės 0.
Sprendimas:
Eilutės, kurios bus sugeneruotos šioms konkrečioms kalboms, yra 000, 0001, 1000, 10001, ..., kuriose 0 visada yra 3 grupėje. Perėjimo grafikas yra toks:
Atkreipkite dėmesį, kad trigubų nulių seka išlaikoma, kad būtų pasiekta galutinė būsena.
5 pavyzdys:
Sukurkite DFA L(M) = {w | w ε {0, 1}*} ir W yra eilutė, kurioje nėra iš eilės einančių 1.
Sprendimas:
Kai atsiranda trys iš eilės 1, DFA bus:
Parsisiųsti youtube vaizdo įrašus į vlc
Taigi čia priimtini du iš eilės 1 arba vienas 1
Etapai q0, q1, q2 yra galutinės būsenos. DFA sugeneruos eilutes, kuriose nėra 1 iš eilės, pvz., 10, 110, 101 ir tt.
6 pavyzdys:
Sukurkite FA, kai ∑ = {0, 1}, priima eilutes su lyginiu skaičiumi 0, po kurio yra vienas 1.
Sprendimas:
DFA gali būti parodyta perėjimo diagrama kaip:
