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
#1 12. 04. 2011 09:28
- karlos.001
- Zelenáč
- Příspěvky: 6
- Reputace: 0
Automaty
Prosím moc o pomoc s následujícím problémem
Vysvětlete, proč pro každé n existuje nedeterministický automat An s n stavy takový, že
minimální deterministický konečný automat přijímající L(An) má 2^n (dvě na n-tou) stavů.
Offline
- (téma jako vyřešené označil(a) gladiator01)
#2 12. 04. 2011 13:01
- gladiator01
- Místo: Jindřichův Hradec
- Příspěvky: 1587
- Škola: ZČU FAV - SWI
- Pozice: absolvent
- Reputace: 53
- Web
Re: Automaty
Přečti si závěr kapitoly 2.1.4 na straně 21,22 zde (soubor progr.jazyky.pdf). Myslím, že tam je vysvětlení.
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 17. 04. 2011 14:08
- karlos.001
- Zelenáč
- Příspěvky: 6
- Reputace: 0
Re: Automaty
↑ gladiator01:
Jako toto mi je všechno jasné, ale nevim jestli neni zaludnost v otazce : vysvetlete proc minimalni dka prijimajici stejny jazyk jako ten nka má
2 na ntou stavu. jaksi mi tam chybi slovicko nanejvys 2 na ntou stavu. protoze on jich muze mit klidne n.
Offline
#4 17. 04. 2011 23:22
- gladiator01
- Místo: Jindřichův Hradec
- Příspěvky: 1587
- Škola: ZČU FAV - SWI
- Pozice: absolvent
- Reputace: 53
- Web
Re: Automaty
Tak já teda nevím, třeba někdo jiný.
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
#6 26. 04. 2011 18:14
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Automaty
Priznam se, ze tomuto tematu temer nerozumim :-) mozna si to jeste vic proctu. Ale napada me: v otazce je "proč pro každé n existuje nedeterministický...", cili bych to chapal, ze sice ten prijimajici automat muze mit obecne n stavu, ale existujou i nedeterministicke automaty, jejichz prijimajici deterministicky jich musi mit minimalne 2^n. Tak mozna uvest priklad, jak pro dane n by ten nedeterministicky automat musle vypadat. Ale jak uz jsem psal, ty materialy sice jsem videl, ale zatim tomu skoro vubec nerozumim :-) tak mozna placam nesmysly.
Offline