"mittedeterministlikud" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

• L(R)={a}, kui R=a • L(R)=∅, kui R=∅ • L(R)={ε}, kui R=ε • L(R)=L(R1)∪L(R2), kui R=R1+R2 (kahe keele ühend, kui R on kahe avaldise summa) • L(R)=L(R1)◦L(R2), kui R=R1R2 (kahe keele konkatenatsioon, kui R on kahe avaldise korrutis) • L(R)=(L(R1))∗, kui R=R1∗ (keele sulund, kui R on avaldise sulund)
 DEF: Regulaarsed avaldised on võrdsed, kui nad defineerivad sama keele. Tehete järjekord: *, ◦, ∪ 3 Deterministlikud ja mittedeterministlikud lõplikud automaadid. deterministlik - igale olekule vastab täpselt 1 järgmine olek Deterministlik lõplik automaat on viisik: M = (Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), q0(lähteolek), F(lõppolekud)). δ : Q × Σ → Q (mingi olek + sümbol tähestikust = uus olek) Mittedeterministlik lõplik automaat on viisik:
 M=(Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), Q0(lähteolekud), F(lõppolekud))