Boris Davidovič (napisa): |
Trebalo bi malo preciznije specificirati što se hoće.
|
Boris Davidovič (napisa): |
Naime, na vježbama jezik je REG = "postoji DKA koji ga prepoznaje". Na predavanjima : REG = "generiran regularnim izrazom", KA = "postoji DKA koji ga prepoznaje". Što se zadatka 1. tiče nema konflikta, jer je lema o pumpanju dokazana nakon teorema KA=REG (s predavanja). Nadalje koristim definicije s predavanja. Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA ⇔ ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. ... |
Boris Davidovič (napisa): |
Kod 2. već imamo konflikt. U predavanjima postoji teorem "KA ⇔ ima konačan skup reziduala", koji je ako uzmemo definiciju s vježbi točno zadatak 2. (ovdje još ne možemo koristiti KA=REG, jer u tom trenu još nije dokazan). Ako pak želimo "REG ⇔ ima konačan skup reziduala", tada moramo dokazati jedan smjer direktno, a drugi pomoću "KA=REG" (možemo i oba preko KA=REG i prethodnog teorema). Pitanje je još koliko treba ići u dubinu dokaza, naime, za teorem "KA ⇔ ima konačan skup reziduala" potrebna je sljedeće lema : |
Boris Davidovič (napisa): |
"L=L(M) za neki DKA M i Q skup stanja od M. TAda card(Q)>=card{Res(L)}", iz koje direktno slijedi zadatak 3. Da li i nju dokazivati? Kako u tom slučaju rješavati 3? |
Anonymous (napisa): |
Što ako ne riješimo neki od teorijskih zadataka? Mislim, ne moramo svi znati sve zadatke, a ako ih prepišemo od nekog onda nema smisla. |
output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.