WERSJA PIERWSZA: MAKSYMALNIE UPROSZCZONA
Operujemy na stosie wartości z pewnego skończonego zbioru. Jest zbiór
reguł: każda oczekuje konkretnego ciągu elementów na szczycie stosu,
zdejmuje go i kładzie inny ciąg. Określony jest początkowy i końcowy
stan stosu. Pytanie: czy istnieje ciąg reguł, które przeprowadzają ten
początkowy stan w końcowy.
Przykład: Reguły: 1 -A-2221
1 -B-2
222 -C-1
31 -D-4
3 -E-44
Stan początkowy: 321
Stan końcowy: 4
Odpowiedź pozytywna:
321 -A-322221 -B-322222 -C-3221 -B-3222 -C-31 -D-4
Dla stanu początkowego 21 i końcowego 4: odpowiedź negatywna.
Ale jak to w ogólnym przypadku znaleźć algorytmicznie? Da się w ogóle?
WERSJA DRUGA: TROCHĘ BARDZIEJ ZBLIŻONA DO TEGO, CO CHCĘ UZYSKAĆ
Zamiast stosu, który składa się z wierzchołka i ogona, mamy drzewo
binarne, które składa się z wierzchołka i dwóch ogonów, z których każdy
jest drzewem albo jest pusty. Reguły oczekują konkretnej postaci kilku
wierzchołków w okolicach korzenia z dowolnymi poddrzewami i obracają
drzewo podczepiając poddrzewa w innej konfiguracji.
WERSJA TRZECIA: JESZCZE OGÓLNIEJSZA
Na razie nie powiem, bo sam dokładnie nie wiem. Poza tym jeśli się okaże,
że nawet pierwszej wersji nie da się dobrze zrobić, to tak czy siak będę
musiał szukać jakichś ograniczeń do nałożenia.
Proszę o jakiekolwiek uwagi na temat.
To jest model konwersji typów.
Mozna probowac tak:
-model ktory przedstawiles, to troche rozszerzony niederministyczny
automat stosowy
(rozszerzenie polega na tym ze zaglada sie kilka pozycji wglab stosu,
mozna to rozwiazac stosujac wiekszy alfabet, tzn. rzedu
rozmiar_alfabetu_wejsciowego^(max_dlugosc_slowa))
pytanie czy z danego slowa da sie przejsc do innego sprowadza
sie do pytania czy dla danego automatu i stosu jezyk generowany
przez ten automat zawiera poszukiwane slowo
-kazdemu nied. automatowi stosowemu odpowiada jakas gramatyka
bezkontekstowa, ktora na dodatek mozna skonstuowac (w druga strone
tez sie da ;-) )
-sprawdzenie czy dane slowo nalezy do jezyka generowanego przez
dana gramatyke bezkontekstowa jest juz w miare proste
(zwlaszcza gdy sie ja sprowadzi do postaci Chomsk'ego) i mozna to
zrobic w czasie wielomianowym
szczegoly mozesz znalezc w notatkach z JAO
(np. http://lipa.mimuw.edu.pl/~rytter)
chyba nawet prostszy problem jest juz dosyc trudny, np. wersja pierwsza
ale dopuszczasz mozliwosc stosowania regul w dowolnym miejscu, to
to juz jest pytanie czy dane slowo nalezy do jezyka generowanego
przez podana gramatyka kontekstowa, i to jest trudne :-((
pozdrowienia
Tomek Walen
Pytanie dotyczy istnienia jakiegos ciagu przeksztalcen, a nie czy
kazda kombinacja zostosowanych regul prowadzi do slowa wyjsciowego
pozdrowienia
Tomek Walen
[ciach!] - racja, dziękuję, wszystko się zgadza. Wygląda niewesoło...
Dobrze by było to tak zrobić, żeby dodanie jednej długiej reguły nie
miało negatywnego wpływu na szybkość sprawdzania wszystkich przejść -
nawet tych, które w danym przypadku nie mają szans z niej skorzystać.
Jednym z ograniczeń, które przychodzi mi do głowy, byłby zakaz stosowania
tej samej reguły dwa razy. W ten sposób zadanie robi się "skończone"
i jedyny problem, to jak to zrobić efektywnie bez sprawdzania wszystkich
możliwości. Takie ograniczenie jest chyba do zaakceptowania, acz trochę
niechętnie.
Sztywne ograniczenie na liczbę użytych reguł to ostateczność, której
chciałbym uniknąć. Podobnie ograniczenie na głębokość stosu; to chyba
prawie na jedno wychodzi.
C++ rozwiązuje odpowiedni problem w ten sposób, że reguły są dwóch
rodzajów. Reguły jednego rodzaju są tak skonstruowane, że się nie
zapętlają i można je znaleźć "na piechotę", znając ich charakter i
wzajemne zależności. Reguł drugiego rodzaju naraz może być użyta tylko
jedna. Ale to mi się nie podoba...
Zrobię jakiś częściowy porządek na przejściach; jeśli istnieje lepsze od
wszystkich innych, to chcę je znać, a jeśli nie, to oczekuję odpowiedzi
"jest, ale niejednoznacznie". Lepsze jest z grubsza takie które jest
podciągiem gorszego.
Reguła może skasować pewną gałąź drzewa całkowicie albo urodzić ją
z niczego, przy czym jeśli dana gałąź miałaby powstać _i_ zniknąć w ten
sposób, to to przejście jest niejednoznaczne. Cały czas problem jest
symetryczny względem odwrócenia reguł i przejścia od końca.
Zamiast "dowolna gałąź" będzie "gałąź spełniająca warunek", gdzie
sprawdzenie warunku może rekurencyjnie pociągnąć za sobą szukanie przejść
między zupełnie innymi parami drzew. To być może sprowadza się do
rozszerzenia alfabetu...
... ale warunki mogą obejmować zestaw kilku gałęzi naraz i tu już zaczynam
się gubić.
Niestety nie widzę, w jaki sposób można wydzielić następną samodzielną
porcję problemu, bez wymyślania wszystkiego równocześnie.
Pb -ab
Zatem jest to wciąż język klasy pierwszej według klasyfikacji
Chomskiego, czyli gramatyka kontekstowa. Tutaj kontekstem jest ta część
stosu, która nie podlega modyfikacji. Żeby taka gramatyka była
bezkontekstowa, to trzebaby opisać produkcje w postaci przekształcającej
cały stos.
Większość znanych mi pozycji z zakresu lingwistyki zaczyna się od
przedstawienia klasyfikacji języków, zaraz po tym jest stwierdzenie
"językami klasy zerowej i pierwszej nie będziemy się dalej zajmować".
Dlaczego? Ano dlatego, że nie wiele się daje z nimi zrobić. Oczywiście
można badać rozbiory metodą brute force, można do niej wprowadzać pewne
heurystyki (np. czy bardziej opłaca się najpierw testować produkcje
wydłużające frazę, czy skracające, czy można założyć, że jedna produkcja
bardziej zbliża nas do frazy docelowej, czy raczej oddala). A odnośnie
czasu wielomianowego - w takiej gramatyce można wskazać, że istnieje
rozbiór o liczności T^F, gdzie T - ilość symboli terminalnych, F -
długość frazy. Powstaje pytanie - czy zatem może istnieć ogólny algorytm
o złożoności niższej od O(T^F)?
Michał
[ciach wsio]
twoja regula [2] uogolniona przypomina bardzo maszyne Turinga, ktora
tez cos czyta, pisze i porusza wprzod i w tyl. Jest tylko jeden
szkopul: nie wiesz, czy ten proces sie kiedykolwiek skonczy. Dlatego
musisz wprowadzic jakies kryteria ograniczajace.
Waldek
Pb -ab
Zatem jest to wciąż język klasy pierwszej według klasyfikacji
Chomskiego, czyli gramatyka kontekstowa. Tutaj kontekstem jest ta część
stosu, która nie podlega modyfikacji.
pozdrowienia
Tomek Walen
Operujemy na stosie wartości z pewnego skończonego zbioru. Jest zbiór
reguł: każda oczekuje konkretnego ciągu elementów na szczycie stosu,
zdejmuje go i kładzie inny ciąg. Określony jest początkowy i końcowy
stan stosu. Pytanie: czy istnieje ciąg reguł, które przeprowadzają ten
początkowy stan w końcowy.
Przykład: Reguły: 1 -A-2221
1 -B-2
222 -C-1
31 -D-4
3 -E-44
Stan początkowy: 321
Stan końcowy: 4
Odpowiedź pozytywna:
321 -A-322221 -B-322222 -C-3221 -B-3222 -C-31 -D-4
Dla stanu początkowego 21 i końcowego 4: odpowiedź negatywna.
Ale jak to w ogólnym przypadku znaleźć algorytmicznie? Da się w ogóle?
Ewentualnie fajnie by bylo miec funkcje heurystyczna i stosowac obciecie
po jakims sensownym progu.
Ponizszy kod prologowy jest brzydki jak nieszczescie (ale chodzi):
------------------------------------------------------------
rule([1|X],[1,2,2,2|X],"A").
rule([1|X],[2|X],"B").
rule([2,2,2|X],[1|X],"C").
rule([1,3|X],[4|X],"D").
rule([3|X],[4,4|X],"E").
s(-1).
f(E,E,X,X).
f(B,E,List,Bag) :-
not(s(B)), assert(s(B)), length(B,Len), Len < 10,
rule(B,N,Name), f(N,E,[Name|List],Bag).
----------------------------------------------------------------
Pozdrawiam,
Staszek