Loading web-font TeX/Math/Italic
Ask Your Question
0

Zjednotenie dvoch automatov

asked Jan 3 '15

gandalf gravatar image

updated Jan 3 '15

Ahojte, chcel by som sa spytat na jednu ulohu.

Je jazyk L regularni? Pokud ano, KA. Pokud ne, formalne dokazat.

L = {a^p: p je prvocislo} zjednotenie {w : w patri {a,b}*, |w| >= 10}

Ako riesit tento typ prikladu? Nasiel som ho aj vyrieseny na fit wiki, neviem ci spravne. Myslel som, ze to bude potrebne robit klasicky, podobne ako sme to robili este davnejsie na cviceni. Tusim sa to vola metoda paralelneho behu alebo tak nejak, no vyrieseny je takto: image description

Staci len pridat startovaci stav a z toho to potom rozvetvit na jeden a druhy automat? A tiez este nerozumiem tej spodnej vetve s prvocislom. Co v pripade napr keby bolo p = 11? Je to tiez prvocislo, no neviem ako by som ho v tomto automate vytvoril. Dakujem.

EDIT: Ospravedlnujem sa, poplietol som prienik so zjednotenim.

add a comment

1 Answer

Sort by » oldest newest most voted
1

answered Jan 3 '15

Lukas Nagy gravatar image

updated Jan 3 '15

EDIT: Takze kedze sa jedna o zjednotenie a nie prienik tak je to v poriadku, i ten automat. Riesis specialny pripad pre prvocisla, tzn jazyk L=\{a^p,p\lt10\} p je prvocislo, co je konecny jazyk takze je regularny. Ostatne pripady spadnu do druhej casti, ktora je regularna takze jazyk je regularny.

link

Comments

No zrejme regularny bude, kedze vzdy v teste jeden je a druhy nie je. Je to z tohto testu https://www.fit-wiki.cz/škola/předměty/bi-aag/aag_test_2014-12-10_1830_neznama a ten druhy regularny nebude urcite, z toho vyplyva, ze ten musi byt :D Mimochodom ja som uplny blbec, poplietol som prienik so zjednotenim... Ospravedlnujem sa, opravim to, a moja otazka smeruje na zjednotenie, nie prienik. Este raz sa ospravedlnujem.

gandalf (Jan 3 '15)

Jasne, super diky :) Cize vzdy ked mam len zjednotenie tak staci pridat pociatocny stav a z toho to rozvetvit, ano?

gandalf (Jan 3 '15)

Su 2 metody zjednotenia, https://edux.fit.cvut.cz/courses/BI-AAG/_media/lectures/03/bi-aag-03-operace_s_automaty-4.pdf [slide12-14] S \epsilon prechodmi je to hned, staci novy stav a prepojit povodne startovne stavy \epsilon prechodmi. S pararelnou cinnostou sa pracuje akoby si naraz chodil 2 cestami, takze mas dvojice a postupne nad nimi robis prechody. pozor! Pri pararelnej cinnosti musia byt oba povodne automaty uplne urcene!

Lukas Nagy (Jan 3 '15)

OK, diky :)

gandalf (Jan 3 '15)
add a comment

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: Jan 3 '15

Seen: 181 times

Last updated: Jan 03 '15