Matematické Fórum
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
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » 2-rozměrný deterministický automat (TOTO TÉMA JE VYŘEŠENÉ)
#1 28. 11. 2010 14:52 — Editoval angmar7771 (28. 11. 2010 15:43)
- angmar7771
- Zelenáč
- Příspěvky: 4
- Reputace: 0
2-rozměrný deterministický automat
Dobry den, mam zadany nasledujici ukol a nevim si s nim moc rady, bych byl vdecny kdyby mi nekdo navedl jak postupovat pri reseni diky ..
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.
Offline
- (téma jako vyřešené označil(a) gladiator01)
#2 28. 11. 2010 15:33 — Editoval gladiator01 (28. 11. 2010 15:33)
- gladiator01
- Místo: Jindřichův Hradec
- Příspěvky: 1587
- Škola: ZČU FAV - SWI
- Pozice: absolvent
- Reputace: 53
- Web
Re: 2-rozměrný deterministický automat
↑ angmar7771:
Jestli chceš aby ti někdo pomohl tak přepiš písmena s diakritikou a symboly, já tam mam jenom čtverečky.
Naděje jako svíce jas, potěší srdce štvané, čím temnější je noční čas, tím zářivěji plane.
VIVERE - MILITARE EST (Seneca)
Vím, že nic nevím. - Sokrates
Offline
#3 28. 11. 2010 15:43
- angmar7771
- Zelenáč
- Příspěvky: 4
- Reputace: 0
Re: 2-rozměrný deterministický automat
gladiator01 napsal(a):
↑ angmar7771:
Jestli chceš aby ti někdo pomohl tak přepiš písmena s diakritikou a symboly, já tam mam jenom čtverečky.
prepsal jsem to .. uz je to videt dobre?
Offline
#4 28. 11. 2010 17:15 — Editoval gladiator01 (10. 06. 2013 20:33)
- gladiator01
- Místo: Jindřichův Hradec
- Příspěvky: 1587
- Škola: ZČU FAV - SWI
- Pozice: absolvent
- Reputace: 53
- Web
Re: 2-rozměrný deterministický automat
↑ angmar7771:
Ano
EDIT: 10.6.2013 Označeno za vyřešené pro neaktivitu.
Naděje jako svíce jas, potěší srdce štvané, čím temnější je noční čas, tím zářivěji plane.
VIVERE - MILITARE EST (Seneca)
Vím, že nic nevím. - Sokrates
Offline
#5 29. 11. 2010 18:02 — Editoval Lumikodlak (29. 11. 2010 18:04)
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: 2-rozměrný deterministický automat
Nikdo zatim se k tomu nevyjadril, nevim co je to automat nebo prechodova funkce ci jak se formuluje jazyk, ale alespon napisu to malo co me napada (mozna ale je ti tohleto naprosto jasne nebo se uplne pletu).
Ta tabulka muze vypadat napriklad takhle:
Code:
############ 0#DPLNDLPNDN# 2#DPDNLPNLPD# 3#LDNLDNPDLL# 4#DNLPLLDNLL# 5#NDLPDLLDLP# 6#DLNDPLLDLP# 7#DLLLPNDPDN# 8#DNLPLDLLLP# 9#NLDLPDPPDL# ############ abcdefghij
Kdyz zacnes napriklad na i7, tak se pokusi vyjet za okraj, zacykli se treba na g4. Ze to nikdy nedosahne koncoveho stavu se mi zda jasne, protoze na kazem policku je posun na jine policko. Tu teorii k tomuto neznam, chvili jsem se dival na internetu, ale nic dostacujiciho jsem nenasel. Ten jazyk se formuluje pomoci pseudokodu, nebo nejakych funkci, nebo jinak, nebo to nevis?
Offline
Stránky: 1
- Hlavní strana
- » Algoritmy a programování
- » 2-rozměrný deterministický automat (TOTO TÉMA JE VYŘEŠENÉ)