Ask Your Question
0

Dokaz neregularnosti jazyka - PL

asked 2014-12-07 14:58:37 +0100

Lukas Nagy gravatar image

updated 2014-12-09 21:12:44 +0100

shejby gravatar image

Vedel by ma niekto nakopnut ako postupovat pri dokaze neregularnosti takehoto jazyka? $$ L={1^n, n \ je\ slozene\ cislo} $$

edit retag flag offensive close delete

2 Answers

Sort by » oldest newest most voted
3

answered 2014-12-07 21:58:56 +0100

Viktor Chlumský gravatar image

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.

edit flag offensive delete publish link more

Comments

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 )edit
0

answered 2014-12-07 21:18:02 +0100

Miro Hrončok gravatar image

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

edit flag offensive delete publish link more

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-12-07 14:58:37 +0100

Seen: 221 times

Last updated: Dec 07 '14