Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Dobry den, mam zadany ukol
2-rozmerny deterministicky automat (2dDFA) je definovany nasledovne.
Vstup je tabulka m x n. Jeji krajni bunky obsahuji symbol # a vnitrni bunky obsahuji symboly ze vstupni abecedy sigma.
Prechodova funkce je zobrazeni Q x Sigma -> Q x (L, P, N, D), kde L=nalevo, P=napravo, D=dolu, N=nahoru. 2dDFA
prijima, pokud vstoupi do koncoveho stavu a zamita pokud se pokusi vyjet za okraj tabulky, nebo pokud nikdy nezastavi.
Uvazujte problem testovani, zda jsou dva 2dDFA ekvivalentni. Formulujte tento problem jako jazyk a ukazte, ze je neresitelny.
Potrebuju dokazat problem ze ekvevilance svou 2dDFA je neresitelny.
Napada me ze bych mohl postupovat takto:
Zredukuju prazdny jazyk (ktery neni castecne rekurzivni) na tento problem a pak ukazu ze doplnek je castecne rekurzivni, ale neni rekurzivni ..
Je tato uvaha spravna? popripade mohl by me nekdo navest spravnym smerem nebo ukazat jak postupovat diky ...
Offline
Tak .. byl jsem na konzultaci a mel bych postupovat nejak takto ...
Ten 2dDFA je specialni verze TS a ja mam dokazat, ze problem ekvivalence dvou 2dDFA TS neni resitelny.
Mel bych postupovat tak, ze dokazu ze ten 2dDFA ma stejnou vypocetni silu jako obycejny TS tzn. ze prijmaji stejnou tridu jazyka a protoze ekvivalence dvou TS je neresitelny problem tak tim je i ekvivalence dvou 2dDFA neresitelny ..
otazka je jak prevest 2dDFA na TS ... 2dDFA ma vstup tabulku a TS pasku takze mam tabulku rozdelit po radcich a zapsat za sebe ? nebo pouzit vice pasek kazdou pro jeden radek te tabulky? A pak ta prechodova funkce, 2dDFA se muze pohybovat doprava, doleva, nahoru i dolu, ale TS jen doleva a doprava takze tam to taky budu muset prevest podle toho jak budu reprezentovat tu tabulku v tom TS ...
nenapada vas nejaky zpusob prevest 2dDFA na TS?
Offline