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 10. 03. 2009 19:00
Jazyky_a_Automaty
Zdravím, doufám, že mi někdo daruje pořádný kopanec kupředu s tímto mým domácím úkolem. Netýká se to sice přímomatematiky, ale doufám, že se tu najde i nějaký informatik.
Myslel jsem si, že tuto problematiku celkem chápu, ale to až do této chvíle, kdy mám spočítat tento příklad.
Zadání:
Uvažujme abecedu Σ = {0, 1}. Ukažte, že jazyků nad abecedou Σ je nespo-
četně mnoho a že (neisomorfních) deterministických konečných automatů pracujících nad
abecedou Σ je spočetně mnoho. Vyvoďte z toho, že musí existovat nespočetně mnoho neregu-
lárních jazyků nad abecedou Σ, zatímco regulárních jazyků nad abecedou Σ je jen spočetně
mnoho.
Rád bych tu napsal alespoň něco co už jsem dokázal spočítat, bohužel nevím vůbec jak začít. Kdyby byl někdo ochoten poradit, byl bych neskutečně vděčný.
Offline
#2 11. 03. 2009 09:04 — Editoval musixx (11. 03. 2009 11:06)
Re: Jazyky_a_Automaty
Každý konečný automat rozhoduje (rozpoznává) regulární jazyk, tedy regulárních jazyků není více než konečných automatů (vzájemně neizomorfních). To, že jsou navíc deterministické nemá žádný vliv, protože každý nedeterministický lze převést na deterministický (taková ta konstrukce, kdy označení uzlu konstruovaného deterministického konečného automatu je nějaká množina uzlů nedeterministického konečného automatu - a podmnožin konečné množiny je stále jen konečně mnoho).
Dále budeme potřebovat alespoň základy teorie množin.
Kolik je nyní neizomorfních deterministických konečných automatů nad abecedou {0,1}? No, to se snadno spočítá. Konečný znamená konečný počet uzlů, mezi libovolnou dvojicí uzlů vedu (či nevedu) orientované šipky s označením 0 nebo 1, tedy konečný počet možností pro jednu dvojici uzlů, počet dvojic je konečný pro daný počet uzlů. Když to všechno posčítám přes všechny možnosti počtu uzlů v automatu, tak se nemohu dostat přes 
, tedy automatů, a proto i regulárních jazyků, je spočetně mnoho.
Dále je jasné, že počet slov nad abecedou {0,1} je alespoň (uvažme třeba slova 1, 01, 001, 0001, 00001, ...), tedy všech podmnožin z těchto vybraných slov je nespočetně, každá taková podmnožina je jazyk a navíc existuje ještě spousta slov, která jsem vůbec neuvážil. Tedy všech jazyků je nespočetně.
"Nespočetno minus spočetno se rovná nespočetno." Proto existuje nespočetně mnoho neregulárních jazyků nad touto abecedou.
EDIT: Poznámka: Analogické argumenty lze použít pro každou neprázdnou abecedu.
Offline
#4 29. 03. 2009 19:00
- caterpillar
- Zelenáč
- Příspěvky: 1
- Reputace: 0
Re: Jazyky_a_Automaty
zdravím nejsem si jistý, že jsem to uplně pochopil nemohl by jsi to trošičku ještě rozvést?
Offline
#5 14. 04. 2009 14:11
Re: Jazyky_a_Automaty
OK díky za radu, která mi zde byla poskytnuta, ale bylo mi řečeno, že co jsem uvedl bylo neúplné řešení, především, že bych měl ještě doložit "algoritmus" pro tvrzení, že je spočetné nekonečno automatů nad jazykem.
Tedy jelikož mám jeden nějaký uzel a ten se mi dělí max na dva další uzly, tedy přechází jedničkou nebo dvojkou, tak mám maximálně dva potomky(bude to tedy jakýsi strom), ale nevím jak to zapsat. Je tedy jasné, že automatů bude nekonečno, ale SPOČETNÉ, zatímco jazyků nad abcedou {0,1} bude NESPOČETNÉ nekonečno.
Offline
#6 14. 04. 2009 20:06 — Editoval NetFenix (15. 04. 2009 07:37)
Re: Jazyky_a_Automaty
Tak teď na tom sedím, tak to zrekapituluji:-)
Jazyků nad abecedou {0,1} je nespočetně nekonečno, regulárních jazyků tj.počet jazyků které jsou rozpoznávány konečnými deterministickými (i nedeterministickými) automaty je spočetně nekonečno. Pokud odečtu nespočetně nekonečno od spočetně nekonečno, výjde, že neregulárnáích jazyků je nespočetně nekonečno.
V této úvaze problém nevidím a i mi bylo řečeno, že je správná, ale teďkom to dokazování o spočetně nekonečném množství automatů mám prý řešit nějakým algoritmem.
To co jsem tu uvedl, bylo nejspíš špatně začaté řešení, tak jsem ho smáznul,
vezmu-li si, že spočetná množina je taková, že se mi všechny prvky z mojí množiny zobrazí do N-bijekce. (tzn., jakože všechny prvky v množině jsou jednoznačně očíslovány), tak patrně budu muset nějak ten algoritmus asi navrhnout tak, aby byl každý automat vždy jasně očíslován nějakým pouze jedním číslem z N.
Asi se bude postupovat tak, že udělám automat pro jeden stav, dva stavy,... ale nenapadá mě jak z toho vyvodit či jak to navrhovat aby mi to do té množiny N padalo:-(
Díky za každou radu a pomoc při řešení tohoto příkladu.
Offline