Matematické Fórum

Redby · 30. 03. 2011 11:56

Ahoj, již několik dní se trápím se sestrojením grafu rozpoznávacího automatu, kterej by měl akceptovat řetězce znaků (a,b) kde rozdíl počtu znaku a a počtu znaků b je dělitelný třemi. Uloha je složitější kde budu dělat průnik grafů a graf splňující první podmínku mám hotovej ale toto ne a ne vyřešit. Díky moc za pomoc

Jookyn · 30. 03. 2011 13:01

Tohle bych asi dělal tak, že bych si napsal příslušnou gramatiku a pak to převedl na automat. Podle mě by gramatika měla vypadat nějak takhle:

S-> aA1 | bB1 | lambda
A1 -> aA2 | bS
B1 -> bB2 | aS
A2 -> aS | bA1
B2 -> bS | aB1

Převod už je pak triviální, za předpokldau, že je tahle gramatika správně, poprosil bych ještě někoho o kontrolu, z automatů už jsem toho spoustu zapomněl...

musixx · 30. 03. 2011 13:34

Automat jde napsat snadno přímo. Má tři stavy, řekněme E, A, B, které znamenají toto:

E ... rozdíl počtu áček a béček je je dělitelný třemi
A ... počet áček mínus počet béček je jedna modulo 3
B ... počet áček mínus počet béček je dva modulo 3

E je jediný vstupní i výstupní stav

Stačí jen snadno uvážit, jak se pod 'a' a 'b' mezi stavy přechází.

Příklad: ze stavu A se pod 'a' přejde do B a pod 'b' do E.

Redby · 30. 03. 2011 14:33

↑ musixx: Díky za radu, akorát mi pořád není jasný kam pujdu béčkem pokud bude jako první znak tedy z E

Jookyn · 30. 03. 2011 15:04

↑ Redby: Do B

Redby · 30. 03. 2011 15:31

Takže by to vypadalo asi takto:

E -> aA ; bB
A -> aB ; bE
B -> aE ; bA

Pokud to tak je tak to akceptuje i řetězec kterej má rozdíl znaků 0. Např ababab

musixx · 30. 03. 2011 15:38

↑ Redby: A tak to má být, ne? Když je tam stejně áček i béček, pak rozdíl v jejich počtu je nula, tedy číslo dělitelné třemi.

Redby · 30. 03. 2011 15:54

Aha, nějak mi nedošlo že je 0 dělitelná 3. V tom případě už jsem to měl vyřešené včera s rozdílem že zbytečně velkej automat. Díky moc. Zkusím je spojit a uvidím co mi s toho vyleze. Kdyžtek zase budu otravovat.

musixx · 30. 03. 2011 16:18

↑ Redby: Je vůbec jazyk, který obsahuje jen slova se stejným počtem áček jako béček, regulární? Není jeden counter ekvivalentní zásobníku? Jak je to s uzavřeností regulárních a bezkontextových jazyků?

Redby · 31. 03. 2011 14:08

V uloze nešlo o jazyk ale jen rozpoznávací automat nad abecedou (a,b). Ale vypadá že to funguje i po průniku s prvním automatem, což je super. Takže ještě jednou díky moc..

musixx · 31. 03. 2011 14:24 — Editoval musixx (31. 03. 2011 14:26)

↑ Redby: Mé otázky směřovaly k tomu, má-li vůbec naději na úspěch hledat konečný automat, který rozpoznává pouze taková slova nad abecedou {a,b}, kde počet áček a béček je různý a přitom rozdíl jejich počtu je dělitelný třemi. Ale to je teď už asi jedno, tvá otázka je zodpovězena.

Matematické Fórum

#1 30. 03. 2011 11:56

Rozpoznávací automat - oříšek

#2 30. 03. 2011 13:01

Re: Rozpoznávací automat - oříšek

#3 30. 03. 2011 13:34

Re: Rozpoznávací automat - oříšek

#4 30. 03. 2011 14:33

Re: Rozpoznávací automat - oříšek

#5 30. 03. 2011 15:04

Re: Rozpoznávací automat - oříšek

#6 30. 03. 2011 15:31

Re: Rozpoznávací automat - oříšek

#7 30. 03. 2011 15:38

Re: Rozpoznávací automat - oříšek

#8 30. 03. 2011 15:54

Re: Rozpoznávací automat - oříšek

#9 30. 03. 2011 16:18

Re: Rozpoznávací automat - oříšek

#10 31. 03. 2011 14:08

Re: Rozpoznávací automat - oříšek

#11 31. 03. 2011 14:24 — Editoval musixx (31. 03. 2011 14:26)

Re: Rozpoznávací automat - oříšek

Zápatí