Zapocet u Petra Hoffmanna

[gASK]

Ale na ten posledni zasobnikovy automat nemuzu prijit...Neco jsem vyplodil, ale to by urcite prijimalo i spatna slova. Jak jste to delali vy?

Za každý Ačko jsem si tam cpal dva znaky (třeba V) a doprostřed (na n-tou pozici) jsem si dal jiný znak (Z). Poté jsem ta každé Bčko odebral V, když jsem se dostal na Z, přehodil jsem stavy...dál už je to snad jasné....

Presne tak jsem to ted udelal taky. Ale jak vis, kam strcit Z? To je prece nedeterministicky krok, ne? Co kdyz to ten automat soupne nekam "blbe" a prijme to kvuli tomu i ilegalni slovo?

Ano, ten automat musí být nedeterministický. To je snad jasné, ne? A nedeterministický zásobníkový automat "pozná" kam a kdy to šoupnout....

Já to tak měl a bylo to dobře... alespoň myslím, zápočet mám

[twoflower]

Za každý Ačko jsem si tam cpal dva znaky (třeba V) a doprostřed (na n-tou pozici) jsem si dal jiný znak (Z). Poté jsem ta každé Bčko odebral V, když jsem se dostal na Z, přehodil jsem stavy...dál už je to snad jasné....

Presne tak jsem to ted udelal taky. Ale jak vis, kam strcit Z? To je prece nedeterministicky krok, ne? Co kdyz to ten automat soupne nekam "blbe" a prijme to kvuli tomu i ilegalni slovo?

Ano, ten automat musí být nedeterministický. To je snad jasné, ne? A nedeterministický zásobníkový automat "pozná" kam a kdy to šoupnout....

Já to tak měl a bylo to dobře... alespoň myslím, zápočet mám

No jasne, vim, ze musi byt nedeterministicky. Jen si myslim, ze kdyz vezmu nejake slovo, ktere do toho jazyka nepatri (nebude platit treba m <= n), tak bude existovat posloupnost operaci toho automatu, pomoci kterych to slovo prijme. A to proto, ze tu zarazku muze vlozit tam, kam se bude hodit

[gASK]

Presne tak jsem to ted udelal taky. Ale jak vis, kam strcit Z? To je prece nedeterministicky krok, ne? Co kdyz to ten automat soupne nekam "blbe" a prijme to kvuli tomu i ilegalni slovo?

Ano, ten automat musí být nedeterministický. To je snad jasné, ne? A nedeterministický zásobníkový automat "pozná" kam a kdy to šoupnout....

Já to tak měl a bylo to dobře... alespoň myslím, zápočet mám

No jasne, vim, ze musi byt nedeterministicky. Jen si myslim, ze kdyz vezmu nejake slovo, ktere do toho jazyka nepatri (nebude platit treba m <= n), tak bude existovat posloupnost operaci toho automatu, pomoci kterych to slovo prijme. A to proto, ze tu zarazku muze vlozit tam, kam se bude hodit

Mno jo no, ale lepší způsob mne nenapadl. Ty nemáš šanci poznat jinak kde je prostředek....

Nejlíp zajít za Hoffmanem samotným na konzultaci...

[snail]

Jina moznost jak to delat bylo si za kazdy acko dat na zasobnik nedeterministicky jeden nebo dva znaky.
Pri cteni becek se pak jeden znak umazaval az jsi narazil na Z.

[twoflower]

Tim Z myslis pocatecni zasobnikovy symbol?

Ted me napadla dalsi moznost - za kazde 'a' pridat dva znaky a za kazde 'b' nedeterministicky smazat bud jeden nebo dva, prijimalo by se prazdnym zasobnikem.

[snail]

Jo, Z - neco co si hodis na dno zasobniku.
To co pises taky funguuje. Moznosti bylo vic.