Matematické Fórum

xy2000 · 04. 03. 2009 16:38

Mohl by mi někdo vysvětlit, jak to řešit?

Navrhněte a detailně popište algoritmus řešící následující problém:
Vstup: Regulární výrazy α a β.
Otázka: Platí [α] ∩ [β] 6= ∅?

Kondr · 04. 03. 2009 19:06

Má se rozhodnout, zda množiny řetězců vyhovujících těm výrazům jsou disjunktní? Co tam dělá ta šestka?

Radar333 · 23. 03. 2009 22:53

Kolega xy2000 to zadani vlozil pomoci ctrl+v a "6=" ve skutecnosti znamena "nerovnase". Nicmene resim stejny ukol jako on a reseni neznam :-( pomuze nekdo?

Kondr · 24. 03. 2009 00:28

Sestrojíme automat pro [a], automat pro [b] a z nich automat pro průnik těchto jazyků. O tomto automatu pak procházením do hloubky zjistíme, zda přijímá alespoň jedno slovo, tedy zda je v něm dosažitelný přijímající stav. Pokud ano, nerovnost platí, v opačném případě ne. Oba dílčí kroky (sestrojení automatu na základě reguláru a sestrojení automatu pro průnik jazyků) jsou popsány ve skriptech http://is.muni.cz/elportal/estud/fi/js0 … maty_I.pdf .

Radar333 · 24. 03. 2009 08:55

↑ Kondr:
díky za rychlou odpověď a odkaz. nicméně řešení bude muset být asi jiné - asi obecnější. totiž regulární výrazy α a β nejsou nikde konkrétně definovány .. pouze je obecně řečeno, že α a β jsou reg. výrazy.

Kondr · 24. 03. 2009 11:53 — Editoval Kondr (24. 03. 2009 11:55)

↑ Radar333:Otázka zněla "popište algoritmus", já jsem popsal algoritmus :) (všechny kroky, ze kterých se skládá, jsou algoritmicky proveditelné). Myslím, že výše popsaný algoritmus pracuje pro všechny dvojice regulárních výrazů korektně. Možná byla moje odpověď trochu matoucí, protože jsem místo [α] a [β] psal pouze [a] a [b].

Radar333 · 24. 03. 2009 12:32

↑ Kondr:
možná bych neměl být z toho zadání tak vyklepaný a lépe číst a více přemýšlet. děkuji za pomoc!

Blade · 28. 03. 2009 18:19

Kondr napsal(a):
............. Oba dílčí kroky (sestrojení automatu na základě reguláru a sestrojení automatu pro průnik jazyků) jsou popsány ve skriptech http://is.muni.cz/elportal/estud/fi/js0 … maty_I.pdf .

Chtěl bych se jen zeptat na které stránce se nacházejí ty dvě témata??? Díky

Kondr · 28. 03. 2009 19:22

Automat pro průnik jazyků: definice 2.9 a věta 2.11 (str. 16)
Automat pro regexp: věta 2.60 na straně 43, k pochopení potřeba přečíst 2.49, 2.52 a 2.53 na stranách 39-40
Číslování beru podle skript, podle PDF potřeba přičíst 5.

Blade · 28. 03. 2009 19:45

Díky moc

Matematické Fórum

#1 04. 03. 2009 16:38

Navrhněte a detailně popište algoritmus řešící následující problém

#2 04. 03. 2009 19:06

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#3 23. 03. 2009 22:53

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#4 24. 03. 2009 00:28

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#5 24. 03. 2009 08:55

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#6 24. 03. 2009 11:53 — Editoval Kondr (24. 03. 2009 11:55)

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#7 24. 03. 2009 12:32

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#8 28. 03. 2009 18:19

Re: Navrhněte a detailně popište algoritmus řešící následující problém

Kondr napsal(a):

#9 28. 03. 2009 19:22

Re: Navrhněte a detailně popište algoritmus řešící následující problém

#10 28. 03. 2009 19:45

Re: Navrhněte a detailně popište algoritmus řešící následující problém

Zápatí