Matematické Fórum

Jazyk je nekonečný, právě když obsahuje takové slovo, že automat při výpočtu nad ním projde jedním stavem dvakrát. Toto je potřeba dokázat (není to těžké) a pak jen najít algoritmus, který hledá v grafu cykly a ověřuje, že alespoň pro jeden z cyklů platí alespoň jedna z podmínek:
a) cyklus obsahuje přijímající stav
b) cyklus lze někde opustit a dojít do přijímajícího stavu
EDITACE: ještě je potřeba, aby ten algoritmus ověřil, že jeden ze stavů v cyklu je dosažitelný
Všeobecně doporučuji přečíst
http://is.muni.cz/elportal/estud/fi/js0 … maty_I.pdf

Algoritmus lze jednoduše popsat také takto
* optimalizujeme vstupní automat
* ověříme, zda výsledný automat obsahuje "peklo" (tj. stav P, který není přijímající a z nějž se libovolným znakem dostaneme opět do P)
* zjistíme, zda automat obsahuje jiný cyklus než P->P. Pokud ano, je jazyk nekonečný, jinak je konečný.

Máme najít algoritmus pro konečné automaty. Tzn. program, který na začátku dostane popis toho automatu (v tvém případě mu zadáme množinu stavů
0,1,2, počáteční stav 0, přijímající 1 a přechodovou funkci
f(0,a)=1
f(1,a)=2
f(2,a)=0
f(0,b)=1
f(1,b)=1
f(2,b)=2)
a náš program z tohoto vstupu vyrobí "ano" nebo "ne" na podle toho, jestli je jazyk konečný nebo ne.
Náš algoritmus tedy (jak jsem psal) víceméně hledá v grafu cykly. Např. procházením do šířky zjistí, jestli se do nějakého stavu dostane cyklem.
Procházením do šířky proti směru hran pak zjistí, jestli se z tohoto cyklu lze dostat do nějakého přijímajícího stavu. Složitost algoritmu je |Q|.|S|, kde Q je množina stavů a S abeceda. Tato složitost je polynomiální.

Lares napsal(a):

Po nalezení cyklu prostě stačí ověřit, zda se z něj nějak nelze dostat do přijímacího stavu.

To je ta myšlenka. Lze ji formulovat i naopak: ověřujeme, že se z přijímajícího stavu dostaneme do toho cyklu proti směru hran. (Kdyby hrany nebyly orientované, dostaneme se z cyklu do akceptujícíh stavu právě když se dostaneme z akceptujícího stavu do cyklu. Protože ale orientované jsou, ta formulace "proti směru hran" je důležitá.)

↑ xy3000:Co to je konečný automat se dočteš na http://bart.math.muni.cz/~brkos/files/d … %C5%AF.pdf . Je tam vysvětlené kdy a jak mění stavy.

Třeba když bych měl  konečný automat který  přijímá regulární jazyk řetězců, které vyjadřují binární číslo dělitelné čtyřmi, tak budu mít stav S0, S1, S2,S3 - to je beze zbytku se zbytkem 1  se zbytkem 2 a se zbytkem 3. Podle čeho ale určím ty přechody a hodnoty kterou ponesou ???

Kondr napsal(a):

↑ xy3000:V tomhle případě je potřeba si uvědomit, co dělá přidání binární cifry 0 nebo 1 na konec slova. Dělá to to, že původní číslo se vynásobí dvěma a ta cifra se přičte.
Konečný automat si o čísle pamatuje jen konečně mnoho informací. V našem případě zbytek po dělení třemi.
Ukážu teď, jak bude automat pracovat, když bude číst vstup 1110
Začínám ve stavu S0, takže to, co jsem načetl doteď, je tvaru 3k. Nyní načtu 1. Celé doteď načtené číslo je 2(3k)+1=3(2k)+1, což dává zbytek 1 po dělení 3. Musím se proto přesunout do S1. Načtu 1. Dosavadní číslo bylo 3n+1, nové je 2(3n+1)+1=3(2n+1), což je dělitelné 3, musím se přesunout do S0. Načtu zase 1. Už víme, že znakem 1 se z S0 dostaneme do S1. Jsme v S1 a načteme 0. Dosud načtené číslo bylo 3m+1, nyní se změnilo na 2(3m+1)+0=3(2m)+2, musím do S2.

Doufám, že je z tohoto příkladu jasné, jak automat funguje a jak doplnit zbylé hodnoty přechodové fce.

Díky za snahu to vysvětlit, je to teda automat na dělení třemi ??? Stále mi není jasné co je to 3k a co je konec slova.

Ještě prosím o vysvětlení 2(3k)+1=3(2k)+1, což dává zbytek 1 po dělení 3. Kde se vezme ten zbytek, respektive jaké číslo musím dělit.
Proč se přehodilo 3k za 2k v těch závorkách.

no a když by to načítalo číslo 1001 tak tedy, S0 3k, S1 3n+1, S2 3m+0 ???
Jde mě to o to jestli se v těch stavech to číslo přesne opisuje, nebo jak se ty hodnoty tam chovají.

Já vím že už s tím moc votravuju, docela už jsem to pochopil, akorát bych jeste prosil o podrobnější vysvětlení těch stavů, který automat právě načetl, stavy S0 , S1, S2. Jak jev tom příkladě číslo 1110    S0 - 3k, S1 3n+1, S2 3m +2 ??Třeba pro číslo 1001.

Kondr - moc díky už to chápu nebo si alespon myslím že to chápu. Poslední otázka pakuž dám pokoj :-). Pokusil jsem se zkonstruovat automat který bude přijímat binární čísla dělitelná čtyřmi. Měl jsem stavy S0,S1,S2,S3. Při výpočtech se mě ale stalo, že jsem přeskočil ze stavu S3 do stavu S1 prostě podle těch zbytků to tak vycházelo, je to dobře nebo blbě, asi blbě co ?

Mám automat přijímající binární čísla dělitelná 4. Zkouším tam pustit číslo 7 - binárně 111 automat by měl skončit v S3. Stav S0 čtu 1 -> 2(4t) + 1 = 8t + 1 , zbytek podle tý jedničky je zbytek 1 tudíž stav S1. Dále stav S1 (8t + 1) = 2(8t+1) + 1 = 16t + 3 , 3:3, zbytek nula stav tedy S0, dále čtu 1 ze stavu S0 tudíž podle dřívějšího propočtu se dostanu z S0 doS1, ale měl bych být v S3, že?

Kondr napsal(a):

↑ xy3000:Ber zbytky po dělení čtyřmi (tj. ne "3:3", jak píšeš...).

no jo to jsem vůl takže teda stav S1 -> 16t + 3 , 3:4 bohužel nevím jak definovat zbytek když dělitel je větší jak dělenec :-((.
Poslední, poslední otázka do jakého stavu půjde tento automat po stavu S1 a proč ??????????