Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:



tharkz

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: tharkz

Autor: j.h

18:47:10 20.12.2010

Jestli už víš, že problém prázdnosti jazyka akceptovaného tímhle automatem není rekurzivní, tak by se to dalo jednoduše ukázat takhle:

Předpokládejme, že problém ekvivalence dvou 2dDFA je rekurzivní. Potom existuje totální Turingův stroj M, který tento problém rozhoduje.
Nechť T je 2dDFA, který každý vstup zamítá.
Pokud na vstup stroje M dáme libovolný 2dDFA Q a automat T, potom M akceptuje právě tehdy, když Q akceptuje prázdný jazyk a zamítá právě když Q akceptuje neprázdný jazyk.
Z toho plyne, že problém prázdnosti je rekurzivní, což je spor, protože problém prázdnosti není rekurzivní.

Je to v podstatě ta redukce, kterou jsi navrhoval.

Citovat příspěvek

 

Re: tharkz

Autor: Alpedar

10:48:02 20.12.2010

Prijde mi to divny. Asi neco nechapu.

Ale uvazuju takto: Je to konecny automat, tedy existuje delka vstupu, od ktere to musi nekterimi stavy prochazet vickrat.

Takze pri zkouseni jestli se dva zachovaji stejne staci overovat konecne mnoho vstupu.


Pristup 2:
Melo by to jit preformulovat jako konecny automat, ten minimalizovat a o pouzit vedomost o zjistovani ekvivalence FA.

Citovat příspěvek

 

tharkz

Autor: redukce TS

11:34:03 15.12.2010

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 ...

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: