asked 2014-12-07 14:58:37 +0100
Vedel by ma niekto nakopnut ako postupovat pri dokaze neregularnosti takehoto jazyka? $$ L={1^n, n \ je\ slozene\ cislo} $$
answered 2014-12-07 21:58:56 +0100
Nevim, kde jste tenhle příklad vzal, ale v téhle podobě je to na pumping lemma docela složitý. Co bych udělal já je, že předpokládám, že pokud je toto regulární jazyk, musí být regulární i jeho doplňek (protože vím, jak případně vyrobit KA přijímající doplňek jazyka).
Stačí tedy dokázat, že doplňek jazyka (tzn. n je prvočíslo, 0 nebo 1) není regulární. Zde by už pumping lemma nemělo být problém.
Priklad je z cvicenia od p. Vagnera...doplnek jazyka by bolo ked n je prvocislo? O takom jazyku viem ze neni regularni, takze jeho doplnek taky neni regularni? EDIT: Jo jasne, neprecital som si koniec, dekuji za radu ;)
Lukas Nagy ( 2014-12-07 22:53:10 +0100 )editanswered 2014-12-07 21:18:02 +0100
Jako nakopnutí bych doporučil použít pumping lemma a fakt, že na toto zadání nelze použít => nejedná se o regulární jazyk. Jak se přesně pumping lemma používá (hlavně formálně) a si už nevzpomínám, ale jde tady o to, že abys tam mohl mít to $n$, tak tam musíš mít cyklus (protože množina všech složených čísel je nekonečná, jinak bys tam pro každé mohl mít větev dlouhou $n$). A tím cyklem můžeš u regulárního jazyka "zapumpovat" (tzn. můžeš se v něm kroutit kolikrát chceš) a pořád to musí být validní. Ale jak pumpuješ tak ti vznikne nesložené číslo.
Otázka je jak sestrojit tu část, kterou se bude pumpovat, aby to na příkladu vyšlo, to už nechám na tobě.
Asked: 2014-12-07 14:58:37 +0100
Seen: 221 times
Last updated: Dec 07 '14
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.
