Matematické Fórum

Co je to (Z)NKA?

↑ Kondr:Díky za ten materíál, ale jak jsem říkal neorientuji se moc dobře v těch značeních a množinách (pomocí čehož to tam zas vysvětlují). Nicméně se chci jen ujistit zda jsem ten převod ZNKA na NKA dobře pochopil. V těch materiálech je tento ZNKA:

A pokud to dobře chápu tak NKA dostanu tak, že se zbavím těch epsilon přechodů. Přičemž stačí vytvořit vždy nový přechod nad určitým symbolem. Tak že např. ze stavu q1 jdu přes 1 do q2 a zároveň jdu z q2 přes epsilon do q1 nebo q0, pak bych měl tedy vytvořit nové přechody pro symbol 1 z q1 zpět do q1 a dále z q1 do q0. Teď můžu epsilon přechody smazat a měl bych mít ekvivalentní NKA. Čili by to mělo vypadat nějak takto:


Ale v tom materiálu co tu je ten NKA vypadá jinak, tak včem dělám chybu. Může mi to teda někdo vysvětlit normalně laicky a polopatě aniž by při tom používal ty množinové zápisy atd. Děkuji za vysvětlení

↑ Zdenek01: Podstatu chápeš dobře. Ještě je potřeba si uvědomit, že původní automat umožňuje jít z q2 přes epsilon a jedničku zpět do q2 a přesepsilon a nulu do q0. Proto je potřeba přidat z q2 přechody pod nulou do q1 a pod jedničkou do q2. A taky se dá jít z q2 přes epsilon,1,epsilon do q0 a do q1, proto je potřeba přidat z q2 přechody pod jedničkou do q0 i q1.

Je proto pohodlnější eliminovat ty přechody po jednom a vždy si nakreslit, jak vypadá automat po odstsranění daného přechodu.

Tak jo zkusil jsem teda ještě jeden příklad, podle Vaší rady viz. obr (v levo ZNKA) v pravo je pak výsledný NKA (ty špatně viditelné hrany jso symboly a a stav 3 má být i výstupní). Potřeboval bych to zkontrolovat


Jinak někde ve skriptech jsem vyhrabal i takovýto postup (nic víc ktomu psané nebylo):
Pokud vede nějaký stav 1 epsilonem do dalšího stavu 2, podíváme se na všechny stavy, které vedou do toho stavu 1 a všechny přechody, které tam vedou přesměruji na stav 2, na který vede náš aktuální epsilon přechod. Pokud je stav stavem vstupním, potom stav, na který vede epsilon přechod se stane také vstupním. Následně se ještě u výsledného NKA zruší nedosažitelné stavy.

Více méně je to ten samý způsob co jsem zde už popisoval.

↑ Kondr: Děkuji za vysvětlení už jsem to asi pochopil, prostě mě jen zmátlo, že jsem to vysvětlení našel ještě ve dvou jiných zdrojích a to bylo v obou případech vysvětleno tak jak jsem to tu už popisoval, proto jsem z toho byl zmaten. Jinak po opravě NKA sedí s tím výsledkem z toho pdf materiálu. Ještě jednou děkuji.

Jinak potřeboval bych vysvětlit ještě jeden příklad viz. http://forum.matweb.cz/viewtopic.php?pid=112323#p112323  Mohl by jste se na něj prosím podívat a zkusil mi nějak vysvětlit řešení? (já v tomto předmětu docela plavu a potřebuji záchranný kruh). Kdyby jste se na ten příklad mrknul, budu vděčný. Děkuju

No když se nato teď tak dívám, tak se mě zdá, že se to dá řešit oběma způsoby (tak jak jsem to popsal já a i tak jak popsal Kondr). V obou případech bude ten NKA ekvivalentní k ZNKA jen jeden z nich bude mít víc přechodů (které jsou tam podle mě zbytečné). Můžete mi to potvrdit?

↑ Zdenek01: Ano, oba výsledné automaty rozpoznávají stejný jazyk. Shoda množin se na množiny vstupních stavů nevztahuje. Jinak mi přijde, že oba automaty slovo 011 přijímají (z q0 do q1, znovu do q1 a nakonec do q2). Nebo něco přehlížím?

↑ Zdenek01: Tak jak je to v odkazovaných skriptech, zůstane zachováno že "ze stavu A do stavu B pod symbolem s se dostanu v NKA, právě když se taam dostanu v ZNKA". Pokud přidáme jen některé přechody (např. algoritmem viz ↑ Zdenek01:), bude toto zachováno jen pokud je stav A vstupní. Pravdou je, že to nám stačí.

↑ Zdenek01: Na 100% věřím řešení ve sriptech a doufám, že je to to samé, co jsem napsal výše. A ten stav vstupní být musí. Uvažme jednoduchý automat, který má stavy p a q. Ze stavu p jde pod nulou zpět do p a pod epsilonem do q, z q jde pod jedničkou do q, q je akceptující. Takový automat přijímá slova, která začínají nulami a pokračují jedničkami, od každého může být nulový počet. Kdybychom q nepřidali do vstupních stavů, přestal by přijímat prázdné slovo a také slovo 11..1.