Zjednotenie dvoch automatov

Question

0

Zjednotenie dvoch automatov

BI
BI-AAG

asked 2015-01-03 12:16:13 +0100

gandalf
113 ●27 ●30 ●37

updated 2015-01-03 12:57:21 +0100

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.

edit retag flag offensive close delete

Accepted Answer

1

answered 2015-01-03 12:48:42 +0100

Lukas Nagy

171 ●6 ●9 ●16

updated 2015-01-03 13:23:00 +0100

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.

edit flag offensive delete publish 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 ( 2015-01-03 12:56:49 +0100 )edit

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

gandalf ( 2015-01-03 13:49:01 +0100 )edit

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 ( 2015-01-03 13:55:07 +0100 )edit

OK, diky :)

gandalf ( 2015-01-03 18:17:07 +0100 )edit

Zjednotenie dvoch automatov

1 Answer

Comments

Your answer

Question tools

Stats

Related questions