Rekursiooni ja keerukusteooria eksami konspekt
DEF: Lõplik automaat on sellise arvuti mudel, millel puudub mälu (või seda on väga vähe).
DEF: Automaadi M keeleks nimetatakse sõnede hulka A, mida M aktsepteerib. L(M)=A
DEF: Keelt nimetatakse regulaarseks, kui seda aktsepteerib mingi deterministlik lõplik automaat.
Reg. keelest saab teha lõpliku arvu sõnesid.
Tehted regulaarsete keeltega:
A∪B = {x|x ∈ A või x ∈ B} ühend nt good, girl, boy, bad
A◦B ={xy|x ∈ A ja y ∈ B} konkatenatsioon nt goodboy,
goodgirl, badboy, badgirl
A∗ = {x1x2...xk|k>=0 ja iga xi ∈ A} sulund nt ε, good, bad, goodgood, badgood…
2 Regulaarsete keelte omadusi. Regulaarsed avaldised.
Teoreem: Regularsete keelte hulk on kinnine ühendi suhtes.
T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1 ja automaat N2 =
(Q2,Σ,δ2,Q20,F2) keelt A2. Eeldame, et keeltel pole ühiseid olekuid.
Ühendi A1 ∪ A2 aktsepteerib lõplik automaat N=(Q;Σ,δ,Q0,F), kus:
• Q = {q0} ∪ Q...