Fórum studentů MFF UK

[quote="mjk"]
Žádná odpověď není označena jako správná, ale pokud dobře vidím, tak ta poslední přesně odpovídá definici ve slidech... přehlížím něco?[/quote]

Myslím, že jsi přehlídnul fakt, že se jedná o obecnej konečnej automat - ne nutně deterministickej. Pro nedeterministickej ani jedna možnost neplatí.

Otázka 102:

Řekneme, že dva stavy [latex]p[/latex] a [latex]q[/latex] konečného automatu [latex]A = (Q,X,\delta,S,F)[/latex] jsou ekvivalentní právě tehdy, když

[latex]\forall w \in X^* : \delta^*(p,w) = \delta^*(q,w)[/latex]
[latex]\forall w \in L(A) : \delta^*(p,w) \in F \Leftrightarrow \delta^*(q,w) \in F[/latex]
[latex]\forall w \in L(A) : \delta^*(p,w) = \delta^*(q,w)[/latex]
[latex]\forall w \in X^* : \delta^*(p,w) \in F \Leftrightarrow \delta^*(q,w) \in F[/latex]

Žádná odpověď není označena jako správná, ale pokud dobře vidím, tak ta poslední přesně odpovídá definici ve slidech... přehlížím něco?

Ta otázka 29 je nějaká divná. Tak jak je napsaná v ní chybí podmínka |v| >= 1, takže si vybereme v = \lambda a jelikož z = uvw = uw \in L, tak i uv^iw = uw \in L pro i >= 0. To by snad mělo platit pro všechny jazyky.

Ahoj, myslím, že je chyba u následujících otázek :

75) Nedeterministický konečný automat má [latex]n[/latex] stavů. Počet stavů po převodu na deterministický nebude větší než:
[list]
[*] nelze říci
[*] [latex]2^n[/latex] stavů
[*] [latex]n^n[/latex] stavů
[*] [latex]n[/latex] stavů[/list]

Jako správné je označeno b a c, ale pro [latex]n^n[/latex] to nebude fungovat pro n = 1. Pokud budeme mít automat s jedním stavem (vstupním a výstupním zároveň), abecedu {0, 1} a smyčku třeba pro 1, nedeterministickému automatu absence nuly nevadí, jenže v deterministickém potřebujeme nějaký "věčně nepřijímající" stav.

Ahoj

Otázka 86)
Správně by mělo být (0*10*1)*0* a 0*(10*1)*0*

Ad otázka 29)
Tady by podle mě mělo být správně jenom regulární, protože pro bezkontextové jazyky ta věta zní trochu jinak.

Jestli nemám pravdu, tak mě opravte.

Jinak by bylo fajn mít možnost zobrazit správné odpovědi k vybrané otázce -> tzn. v zobrazení všech otázek buď správné odpovědi vyznačit nebo po kliku na tlačítko "Zobrazit test" zobrazit zvolenou testovou otázku.

//Edit:
Tak jsem se dneska na zkoušce přesvědčil, že moje doměnka k otázce 29 je špatně :D
PS: až se budete učit na zkoušku a budete si říkat, že ty největší hnusárny tam být nemůžou... Můžou :D

Zdravim,

otazka 29) pumping lemma plati pro jazyky:

spravna odpoved je uvedena "regularni, bezkontextove a kontextove" a pro kontextove jazyky rozhodne neplati (protipriklad na slidech - a^i b^j c^k (1 <= i <= j <= k) nemuzu nikde pumpovat pro vsechna cisla od nuly vcetne, protoze kazde pismeno tam musi byt aspon jednou. A i kdyby, libovolnym pumpovanim v kterekoli casti drive ci pozdeji porusim nejakou nerovnost.

Ahoj, to je nepochybně pravda, díky za upozornění, už jsem to tam opravil.

Ahoj,

u otazky 44) Jazyk {1^k 1^k 0^l | k, l >= 0} je podle me spravne i odpoved regularni. Je to prece {1^2k 0^l | k, l >= 0} a protoze neni definovany zadny vztah mezi k a l, tak k tomu jde jednoduse sestrojit automat, ktery ten jazyk prijme.

Mira

Zdravím, tak jsem tam tedy doplnil ještě otázky od mathemage.

pravda, omlouvám se, to jsem přehlédla.

Ta odpověď je správně. Pozor, u tý otázky se jedná o NKA, neboť je tam S jako množina počátečních stavů, tedy ani jedna z odpovědí nedává smysl.

super udělátko, díky moc :)

u otázky 95, (týká se ekvivalentních stavů - nechce se mi to sem přepisovat) není uvedena správně žádná možnost, ale viz slajdy by měla podle mě být správně odp. 0. (je to definice)
pokud se mýlim, tak se omlouvám a případně prosím o vysvětlení.

Díky, otázku jsem opravil, myslím, že tam asi bude chyb více, když bych něco objevil, tak to sem napíšu. Ty zbylé tam doplním někdy během příštího týdne.

Ve stavovém diagramu libovolného deterministického konečného automatu (hrana je určena dvojicí stavů a písmenem) vede z každého stavu:
A) právě tolik hran kolik je písmen v abecedě
B) právě jedna hrana
C) alespoň jedna hrana
D) méně hran než kolik je stavů

Moc pěkné, ještě bys tam mohl doplnit otázky, které sem dává *mathemage*: [url]http://forum.matfyz.info/viewtopic.php?f=243&t=8286[/url]

Jo a ještě bych chtěl upozornit na jednu otázku, konkrétně:

[code]Ve stavovém diagramu libovolného deterministického konečného automatu (hrana je určena dvojicí stavů a písmenem) vede z každého stavu:
A) právě tolik hran kolik je písmen v abecedě
B) právě jedna hrana
C) alespoň jedna hrana
D) méně hran než kolik je stavů[/code]
Tuhle otázku jsem tu někde našel na fóru zodpovězenou, s odpovědí jenom "A". Ale já bych dal "AC", protože imho musí být abeceda neprázdná. Imho to je zkoušítku označeno jenom jako "A", tak to kdyžtak oprav.

Zdravím, trochu jsem to ještě přepracoval a hodil k sobě na stránky pro ty, kteří nemají instalováno PHP, pořp. si jej instalovat nechtějí nebo jsou moc líní.

http://www.skvaril.net/cz/automaty/