Regular Sets

Question 1

Zakaj se uporablja Lemma o napihovanju?

Answer 1

1. za dokazovanje da določeni jeziki niso regularni

2. za dokazovanje da so jeziki določenih KA končni oz. neskončni

Question 2

Opiši Lemmo o napihovanju!

Answer 2

Naj bo L regularna množica. Potem obstaja taka konstanta n, kjer je n največ lahko število stanj:
 Če je:
   z ∈ L in |z| >= n
 Potem obstaja u, v, w tako da:
   z = uvw, in
   |uv| <= n, in
   Vsaki i > 0: u(vnai)w ∈ L

Za vsak ustrezno dolgo besedo z, ki jo sprejme KA, lahko najdemo podbesedo v, ki jo lahko ponavljamo (napihujemo) kolikokrat hočemo, ampak končno besedo bo KA še zmeraj sprejel.

Question 3

Stroga definicija Lemme o napihovanju :)

Answer 3

L regular => (∃n)(Vs z)[z ∈ L IN |z| >= n => (∃u,v,w)[z = uvw IN |uv| <= n IN |v| >= 1 IN (Vs i > 0)u * v na i * w ∈ L]]

Question 4

Kaj so odločilni problemi in kaj so odločilni algoritmi?

Answer 4

Odločilni problemi so problemi, ki sprašujejo po JA/NE odgovorih. Algoritmi, ki rešujejo takšne JA/NE probleme, so odločilni algoritmi.

Question 5

Kdaj sta dva avtomata M1 in M2 ekvivalentna?

Answer 5

Avtomata sta ekvivalentna kadar sprejemata enak jezik (L(M1) = L(M2)).