Matematické Fórum

↑↑ Kondr:

Proč by to bylo špatně? Já vim, že tam může být těch cyklů spousta a ty automaty můžou vypadat jinak (taky kdyby vypadaly stejně - stejný počet stavů, stejný propojení tak by nebylo co řešit).
To co píšu neni nějak formálně neprůstřelný jako ten algoritmus jak je popsanej v tom pdf nebo ta soustava rovnic co by šla řešit, ale tak mi připadá, že by to mohlo co nejvíc odpovídat tomu co popisoval marros.

Neměl sem teď moc čas tak sem chodil pokukovat spíš jenom do střední školy :) teď se tady o tom rozepíšu...

↑↑ marros11:
Nejdriv k tomuhle:

Jeste bych mel dotaz, bylo mi receno ze si mam predstavit ty dva automaty jako ze prijimaji jednotliva slova a pak ze je nejaka jedna ridici jednotka, ktera vyhodnoti jestli oba automaty prijimaji tytez slova. Ztoho lze odvodit jestli jsou ekvivalentni.

Teď mě napadlo, že tím možná myslel tohle:
Ta řídicí jednotka jak o ní píšeš by mohla generovat všechny mozný kombinace nad vstupní abecedou a pak je postupně dávat na vstup každýho toho automatu. Pak v momentě kdy jeden automat nepřijme a druhý přijme tak je odpověď že automaty nejsou stejny.
Teď ale zajímavá otázka jak dlouho generovat ty vstupní kombinace, resp. do jaký délky generovat ty vstupní slova??? Jelikož vstupní slovo může být libovolně dlouhý (protože těch kombinací je nekonečno) tak kdyby ty automaty byly stejný tak bys pořád jenom generoval a nikdy by ses nezastavil... Takže musíš nějak omezit tu délku generovanýho slova. A tu dýlku bych omezil na počet stavů toho automatu, který má víc stavů. Proč??? Počet stavů je dejme tomu n, pak když vygeneruješ všechny slova do délky < n tak když ten automat přijímá toto slovo tak musí projít všema svýma stavama!!! (Resp. když přijme všechy slova délky < n aby to bylo úplně správně napsaný). Když vygeneruješ slovo o délce n, tak už se musíš v tom automatu vrátit do nějakýho stavu, ve kterém si už dřív byl!!! To znamená, že poslední symbol toho slova o délce n je začátek cyklu. Teď se stačí podivat u obou automatů v jakym si stavu (do jakýho stavu si se tou smyčkou vrátil) a jaký další může mít ten řetězec pokračování? Jak to zjistíš? No tak že v tom stavu si už určitě někdy byl (když si zkoušel jestli ten automat přijme všechny ty možný kombinace do dýlky < n). Takže sis třeba někam zapamatoval u obou automatů jaký řetězce můžeš  z toho stavu přijmout...

Určitě by to co sem teď napsal šlo nějak vylepšit nebo napsat nějak formálnějc, takže jestli někoho něco napadne tak šup sem s tim, taky nad tim ještě popřemejšlim

Teď k tomu jak si se ptal dřív:

V tom prispevku jak jsi se rozepsal jak by to slo resit, slo by to zformulovat do nejakych obecnych kroku?

Původně sem to myslel opačně...prostě bys procházel těma automatama a sepisoval si všechny řetězce, který přijímají. Zase, těch "originálních" řetězců (tim myslim bez cyklu) je omezenej počet a je omezenej právě na ten počet stavů, pak už se musí začít něco opakovat. Takhle by sis ty řetězce sepsal, pak bys je musel porovnat a pak v těch řetězcích identifikovat ten cyklus a zjistit jestli se u obou automatů shoduje...Podle toho bys pak moh lehce najít a nějak vyznačit přesně ten cyklus v těch automatech a nějak graficky to třeba zakroužkovat a ukázat jakože si ty cykly odpovídají...prostě tim myslim, že bys jako ukázal, že si odpovídají jednotlivý ty části těch automatů...

To co sem psal ale teď na začátku s tím generovánim vstupních řetězců mi momentálně přijde lepší...

Jinak na tu redukci mrknu navečer...

↑ xxsawer:Nedosažitelný stav je takový, do kterého se nelze nikdy dostat. Třeba automat se dvěma stavy, jeden z nich je počáteční, přijímající, a jakýmkoliv symbolem se přejde z něj do něj samého. Je zřejmé, že ten druhý stav můžeme vypustit a nic se nezmění, nicméně pohá "jazyková nerozlišitelnost" nám ho neodstraní (např. proto, že dosažitelný stav jsme zvolili jako přijímající a nedosažitelný ne).

↑ xxsawer:Dekuji moc za supr rozbor, vypada to ze by to mohlo fungovat. Lehce jsem pozmenil ten text, tak abych to mohl hodit do toho referatu, tady je vysledna podoba:

1. V prvnim kroku prevedeu RV na DKA
2. Provedu odstraneni nedosazitelnych stavu
3. Algoritmus od xxsawer:

V dalším kroku budu vycházet z předpokladu, že mám řídicí jednotku, která bude generovat všechny možné kombinace nad vstupní abecedou a bude si pamatovat stavy obou automatů. Generované slova pak bude postupně dávat na vstup každého automatu. Pak v momentě kdy jeden automat slovo nepřijme a druhý přijme, tak je odpověď že automaty nejsou ekvivalentní.
Zůstává otázkou jak dlouho generovat ty vstupní kombinace, resp. do jaké délky generovat ty vstupní slova? Jelikož vstupní slovo může být libovolně dlouhé (protože těch kombinací je nekonečno) tak kdyby ty automaty byly stejné tak by se pořád jenom generovali nová slova a nikdy by se cyklus neukončil. Takže se musí omezit délka generovaného slova. A tu délku omezíme na počet stavů toho automatu, který má víc stavů. Počet stavů je např. n, pak když vygenerujeme všechny slova do délky < n tak když automat přijímá toto slovo tak musí projít všema svýma stavama. (Resp. když přijme všechny slova délky < n). Když vygeneruje slovo o délce n, tak už se musí v tom automatu vrátit do nějakého stavu, ve kterém už dřív byl. To znamená, že poslední symbol toho slova o délce n je začátek cyklu.
Teď se stačí podívat u obou automatů v jakém je stavu (do jakého stavu se tou smyčkou vrátil). Jaké další může mít ten řetězec pokračování? To zjistíme tak že v tom stavu už určitě někdy byl (když jsme zkoušeli, jestli ten automat přijme všechny ty možné kombinace do délky < n). Když budeme mít někde uložené u obou automatů jaký řetězce můžeme z toho stavu přijmout, jsme schopni porovnat, jestli přijímají stejná slova.

Chtel bych se zeptat jestli ten prepis je platny, jestli jsem mirnou upravou textu nepozmenil vyznam tvoji myslenky.

Dekuji.

↑ marros11:

Ještě nejdřív k těm nedosažitelným stavům.
Tady sem nakreslil obrázek, ze kterýho to bude jasný



Stavy Q3 a Q4 jsou nedosažitelný protože do nich z počátečního stavu prostě neexistuje žádná cesta.
Takovýhle stavy ti tam nijak nevzniknou ktyž budeš převádět RV na DKA takže bych vynechal ten bod 2.

Ukázku toho mýho algoritmu aby bylo úplně jasný jak to myslim
Tady jsou dva automaty, který máš porovnat:



Vstupní abeceda je pro jednoduchost jenom a.
První automat přijímá řetězce a-ček o dýlce 2, 5, 8, 11, ...
Druhej automat přijímá řetězce a-ček o dýlce 2, 4, 6, 8, ...

Automat má tři stavy, takže podle toho co sem psal před tím budem generovat řetězce do dýlky 3 včetně.
a ... neni příjímán ani jedním automatem
aa ... je přijímán oběma automaty

V tomhle okamžiku jsme dorazili do koncovýho stavu a ke každýmu stavu (kterým jsem prošel) si poznamenám jaký řetězec z něj (tím myslím jako kdyby ten stav byl počáteční) můžu přijmout. Takže ze stavu Q1 kdyby byl počáteční (což náhodou v tomhle případě je) můžu přijmout řetězec aa. Ze stavu Q2 kdyby byl počáteční můžu přijmout řetězec a. Tohle je tedy u obou automatů stejný.

aaa ... neni přijímán ani jedním automatem, ALE protože délka řetězce = počet stavů, tak se podivám do tabulky toho stavu, ve kterym momentálně sem, "přičtu" k aktuálnímu řetězci všechny ty řetězce, který mám v tý tabulce (ale postupně, takže když budu mít v tabulce 3 údaje tak mi vzniknou tři různý řetězce se stejnym prefixem a lišit se budou v suffixu). V tomto případě tedy dostanu řetězec aaaaa - v případě prvního automatu. V případě druhýho automatu dostanu aaaa. Řetězce se nerovnají -> automaty nejsou stejný.

Teď ten algoritmus jak by to šlo odprezentovat...

1. V prvnim kroku prevedeu RV na DKA
2. Předpokládám, že mám jednotku, která postupně generuje všechny možné řetězce nad vstupní abecedou (od nejkratších řetězců po delší) a dává je na vstup oběma automatům. Jakmile jeden z automatů přijme a druhý ne, algoritmus končí -> automaty nejsou stejné

Jelikož délka řetězce není omezená, je takovýchto řetězců nekonečně mnoho a pokud by byly oba automaty shodné, algoritmus by nikdy neskončil - generoval by do nekonečna řetězce čím dál větší délky a dával je postupně na vstup oběma automatům. Musíme tedy nějak omezit délku generovaného řetězce. Vycházíme z úvahy, že pokud má automat n stavů, tak pokud vygenerujeme všechny možné řetězce nad vstupní abecedou do délky n-1 a dáme je na vstup automatu, tak máme jistotu, že jsme každý stav "navštívili" alespoň jednou (neuvažujeme nedostupné stavy). Pokud vygenerujeme řetězec délky n tak je zřejmé, že jsme v některém stavu museli být minimálně 2x. Formálně zapsáno:

Jednotka tedy bude generovat všechny možné řetězce nad vstupní abecedou délky <= n (kde n je počet stavů automatu, který má více stavů). Jednotka si u každého stavu pamatuje "jaký řetězec je z tohoto stavů přijímán" kdyby byl tento stav počátečním stavem, viz příklad...
Pokud tedy dáváme automatům na vstup řetězce délky n, vždy se podíváme do tabulky pro příslušný stav (což je stav do kterého jsme se dostali postupným přijímáním námi vygenerovaného řetězce délky n) a provedeme konkatenace (zřetězení) vygenerovaného řetězce s údaji v tabulce a to tak, že námi vygenerovaný řetězec bude tvořit prefix a každý řetězec v tabulce bude tvořit suffix výsledného řetězce. Toto provedeme pro oba automaty a výsledné řetězce obou automatů mezi sebou porovnáme. Pokud nenajdeme shodu, automaty NEJSOU stejné, pokud shodu najdeme, automaty JSOU stejné. V obou případech algoritmus končí.

Myslim, že takhle bys to moh podat. Jinak taky nevim jestli je to správně a funguje to 100% pro všechny automaty, tohle mě prostě napadlo a ten princip vychází z důkazu pumping lemmy pro regulární jazyky, tak si myslim, že by to mohlo být v pohodě.