Skończoność pliku gramatyki

Witam, mam pewien projekt do zrobienia w C++ tylko mam duuuzy kłopot z wymyśleniem algorytmu. Mam na przykład sytuację:
@>aB
@>fD
A>cB
A>dE
B>bA
C>eD
D>gE
D>hG
E>aD
G>dH
G>b
H>eG
Ten ciąg znaczków powyżej to jest lista reguł do zastosowania. Te reguły są przedstawione za pomocą tablicy dwuwymiarowej: reguly[ilość_reguł][2], znak ”>” nie zalicza się do budowy reguły. Program ma działać w taki sposób, że począwszy od symbolu startowego którym jest '@', stosujemy np. losowo reguły tak aby w ostateczności dostać wyrażenie składające się tylko z małych literek, np: @->fD->fhG->fhdH->fhdeG->fhdeb. Wszystko mi pięknie działa...podstawianie reguł, tworzenie ostatecznego wyrażenia złożonego z małych literek tylko mam jeden kłopot. Jeśli reguły są źle skonstruowane, dzieje się tak, że wykonując kolejne podstawienia, dochodzi do zapętlenia - czyli następuje podstawienie znaków i tak w kółko, czyli nie ma skończonego wyrażenia. No i pytanie moje brzmi, czy może ktoś z Was zna algorytm na wyznaczenie czy zbiór reguł jest skończony, czy też nie? Proszę bardzo o pomoc...Z góry dziękuję za wszelkie próby rozwiązania tego w sumie ciekawego problemu!

P.S. Sorki za umieszczenie tego samego problemu w temacie "1 rok informatyki - algorytmy/projekty "

Gdy mam do wyboru więcej niż jedną, pasującą regułę, to którą należy wybrać?

Ogólnie trzebaby tu pokombinowac. Na poczatek: sprawdzenie, czy jest jakikolwiek znak, któremu odpowiadający znak podmiany jest jedynie małaa literą. Jeśli nie- znaczy będzie się zapętlał.
Potem przychodzi mi tak na razie do głowy tylko rozpoczynanie i sprawdzanie wsyzstkich możliwości, brut force. Ale to metoda strasznie kiepska i tutaj nawet się nie sprawdzi (nawet na dobrych danych moze się zapętlic, patrz A>cB B>bA).
Czuję, że tutaj coś z grafami będzie...
Na początek co? Szukanie cykli? Nie, może być cykl, byle dało się z niego wyjśc. Trzebaby więc sprawdzić, czy z każdego cyklu można jakoś dojść do wyrazu końcowego, czyli tego, gdzie jest tylko mała litera. A jeżeli nie ma cyklu, to sprawdzenie, czy z któregokolwiek wyrazu da się dojść jakoś do wyrazu końcowego.
Z któregokolwiek wyrazu - rozumiem przez to wszystkie wyrazy do których da się wejść, jeśli są jakieś wierzchołki niepołączone (nie pamiętam jak się to nazywa :P ) to nie trzeba tego wierzchołka sprawdzać bo i po co, jeśli się do niego nie da wejść, to wyjść nie trzeba sprawdzać.
Ogólnie kombinuj w stronę grafów. A o grafach to już masa powinno na necie byc.

Więc tak! Reguły wybierane są losowo. Więc jak są np. 2 lub więcej do wyboru to po jednym uruchomieniu programu zostanie wybrana pierwsza a innym razem druga. Chodzi o to żeby zabezpieczyć się przed sytuacją, kiedy mamy np. taki zestaw reguł:
@>aA
A>cB
B>d
B>aC
C>cC
I następuje sytuacja, że zostaje wylosowana reguła B>aC następnie: acC -> accC -> acccC ... i tak dalej i mamy zapętlenie. To jest stosunkowo prosty przykład ale jeśli jest zapętlenie spowodowane wylosowywaniem 2 lub więcej reguł, to ciężko jest jakiś algorytm na to wymyśleć. Proszę o pomoc i dzięki za zainteresowanie sie tematem! Pozdrawiam

Tak jak mówi poprzednik można ten problem sprowadzić do szukania dowolnej ścieżki między dwoma wierzchołkami w grafie. Jedynie co tu może być troche trudniejszego dla pierwszego roku to utworzenie grafu na podstawie listy reguł.

Stworzenie grafu nie powinno być w sumie nawet takie złe, każdą regułę można ponumerować i w macierzy ładnie oznaczyć przejścia między węzłami (wiersz to węzeł w którym jesteśmy, kolumny to węzły do których możemy iść). A potem tylko algorytmy na szukanie ścieżek z każdeg pkt do pkt końcowego jakiegoś, czyli takiego, który nie łączy się z żadnym innym.
Z tymi algorytmami to mógłby właśnie być raczej problem, zęby się nie zapętlać i nie liczyć w nieskończoność, ale może gdzieś na necie juz cos bedzie.

Algorytm to żaden problem, wystarczy zapuścić BFSa albo DFSa i przerwać gdy znajdzie się wierzchołek bez krawędzi wychodzących.

Dzieki wielkie za pomoc. Z tymi algorytmami to juz wielki krok na przod!!! Chociaz zimplementowalem ten algorytm, ale dalej mam klopot. Pozwól, ze pokaże go na przykładzie:
Algorytm przeszukiwania...obojetne czy BFS czy DFS wypluł mi kolejne przejcia ze stanu do stanu, np. jak tu poniżej:
0 -> 2
0 -> 4
1 -> 2
1 -> K
2 -> 2
2 -> 3
3 -> 2
4 -> K
K u mnie oznacza "kończącą" czyli w momencie kiedy przeglądając graf, napotkamy na kończący symbol...czyli odpowiednik pustego symbolu, to jest OK - gramatyka jest skonczona jesli chodzi o dana regule. Ale jak w przykładzie powyżej pojawia sie klopot!!! Jesli wziasc pod uwage przejscia ze stanów:
2 -> 2
2 -> 3
3 -> 2,
każde z nich ma krawędź wychodzącą, więc warunek który zaproponowałeś, jest spełniony ale niestety to nie wystarcza i się zapętla:( no i nasuwa sie wlasnie pytanie: jak rozpoznasz taką sytuację? Proszę bardzo o pomoc! Pozdrawiam miłego piątku;)

Po prostu algorytm nigdy nie może przejść dwa razy po tej samej gałęzi. Jeśli raz już dana gałąź była odwiedzona (na przykład przejście 2->2) to drugi raz nie można nią przechodzić. Dzięki temu program nie zapętli się, co najwyżej stwierdzi, że znalazł takie przejście, z którego nie można nigdzie dojść, wtedy będzie sie wycofywał aż dojdzie do pkt, gdzie może wybrać inne wyjście (te, z których się wycofywał pozostają oznaczone jako odwiedzone) i próbował inną trasę.

ciach - napisalem strone tekstu a potem przeczytalem temat watku:)) tak to jest jak sie przeglada pol setki watkow po kolei..

co do skonczonosci zbioru regul - sprawa jest dosc prosta. rozwijanie ma szanse osiagnac koniec wtedy i tylko wtedy jesli kazda regula ma_szanse dojsc w rozwinieciach do reguly ktora sklada sie tylko z symboli terminalnych, np:

1: @->aA
2: A->bB
3: B->bA
4: B->bc

przegladamy reguly kolejno i oznaczamy:
1-sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
2-sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
3-sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
4-sa same terminalne, wiec skonczona

czesc regul dostala nowy stan, wiec powtorka:
1-sa nieznane nieterminalne, wiec nie wiadomo
2-sa nieterminalne, ale wszystkie sa skonczone, wiec regula jest skonczona
3-sa nieterminalne, ale wszystkie sa skonczone, wiec regula jest skonczona

czesc regul dostala nowy stan, wiec powtorka:
1-sa nieterminalne, ale wszystkie sa skonczone, wiec regula jest skonczona

czesc regul dostala nowy stan, wiec powtorka:
koniec regul, wiec koniec

wszystkie @ stanely na stanie 'skonczona' wiec wszystkie zdania z gramatyki sa skonczone.

inny przyklad:

1: @->aA
2: A->bABC
3: B-> bA
4: C-> c
przegladamy reguly kolejno i oznaczamy:
1 - sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
2 - sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
3 - sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
4 - same terminalne, wiec skonczona

czesc regul dostala nowy stan, wiec powtorka:
1 - sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo
2 - sa nieterminalne i niektore sa "byc moze nieskonczone", wiec nie wiadomo
3 - sa nieterminalne i sa one "byc moze nieskonczone", wiec nie wiadomo

nie odnaleziono nowych skonczonych, wiec koniec badania.

jedna z regul startowa @ stanela na 'nie wiadomo', wiec ten zestaw jest "nieskonczony"

zlozonosc badania - N^2 gdzie n=liczba regul. oczywiscie, mozna to zrobic inteligentniej, ale napisac w/w test to kwestia paru minut :)

co do znanych algo, rzeczywiscie mozna to porownac do wyszukiwania sciezek:

• jesli od KAZDEJ @ da sie dojsc do jakiejkolwiek reguly 'terminalnej', to zbior regul jest 'skonczony'
  ew.
• jesli od jakiejkolwiek @ nie da sie dojsc do ZADNEJ reguly 'terminalnej', to zbior jest 'nieskonczony'

Wielkie dzienki za tak dluga i dokladna odpowiedz...ale prosze jeszcze o jedno jesli mozna. Jak znajdziesz chwilke to napisz prosze jak mozna sie zabrac do tego od strony C++ bo algorytm jest w miare jasny...tylko troche ciezko mi sobie to przelozyc na wlasciwy kod bo jesli chodzi o programowanie to nie jestem zbyt doswiadczony;/ tzn chodzi mi przede wszystkim o to jakiego typu algorytmow uzywac...czy do analizy grafow...czy to w ogóle nie ma z tym nic wspolnego?, jak mozna np. juz jesli chodzi o pisanie kodu zrodlowego zaznaczyc czy np. oznaczyc, czy regula jest "byc moze nieskonczona", i co oznacza, ze regula dostala nowy stan? po prostu nie za bardzo jestem w stanie ogarnac w jakiej kolejnosci sprawdzac zaleznosc regul od siebie i to czy w efekcie dotrą one do koncowego symbolu terminalnego, czy też nie.
Myslalem jeszcze ze mozna to zrobic w ten sposob ze zaczynajac od glowy gramatyki '@', wypisac wszystkie mozliwe przejscia bez wykonywania cyklu wiecej niz raz, a pozniej sprawdzic czy istnieje taka sciezka, ktora która jest zakonczona symbolem nieterminalnym. Jesli taka sciezka istnieje, oznacza to ze gramatyka jest nieskonczona. Tylko w ogóle nie wiem czy taki algorytm istnieje. Proszę o jakieś dodatkowe wskazówki.
Pozdrawiam

ok.. zalaczam zrzut z GG dotyczacy badania skonczonosci zdan gramatyki:

info: zakladam, ze chcemy sprawdzic czy zbior regul bedzie generowal zdania skonczonej dlugosci, ale -- uwaga -- zezwalamy na mozliwosc DOWOLNIE DLUGICH zdan. tzn.

@-> A
A-> aA
jest nie-skonczone

@-> A
A-> aA
A-> a
jest skonczone, ale nieograniczone

@-> A
A-> a
jest skonczone i ograniczone

za "skonczone" gramatyki, ponizszy przyklad uznaje typ DRUGI i TRZECI.
jesli wg. "Twojej definicji" jedynie typ trzeci jest skonczony, coz, bedziesz musial(a) naniesc modyfikacje;)

wezmy na przyklad reguly
1: @->aA
2: A->bB
3: B->bA
4: B->bc

macierz przejsc dla tych regul wyglada mniejwiecej tak:

wiersze-skad, kolumny-dokad
@ A B
@ - o -
A - - o
B - o -
B - - -

to jest zobrazowanie ktora regula do ktorej moze prowadzic. np. @ prowadzic do A, ze regula B(1) prowadzi do A, a regula B(2) prowadzi do zadnej

szukamy bezpicznych - bezpieczna jest regula ostatnia, poniewaz do nikad nie prowadzi dalej.
skoro symbol nieterminalny 'B' moze prowadzic do skonczenia sciezki, to symbol ten jest bezpieczny - jego uzycie gwarantuje ze kiedys-tam, w koncu, wszytkie jego rozwiniecia wylosuja 'zakonczenie'.
usuwamy reguly rozwiniec symbolu B, bo juz wiadomo ze jest on bezpieczny i nie ma go co dalej analizowac

@  A   B

@ - o -
A - - o
X X X X
X X X X

czyli

@  A   B

@ - o -
A - - o

teraz.. skoro B jest bezpieczny, to po co zawracac sobie glowe ze symbol A moze do niego prowadzic? B jest bezpieczne tak jak i '-'

@  A   B

@ - o -
A - - -

albo wprost

@  A 

@ - o
A - -

bo po co komu B..

patrzymy dalej -- szukamy bezpiecznych. bezpieczna jest regula druga, poniewaz wszystkie jej "cele" sa bezpieczne. usuwamy ja, oznaczamy A jako bezpieczne

@ X 

@ - X
X X X

czyli

@  

@ -

patrzymy dalej: szukamy bezpiecznych. wszysko chyba widac.. usuwamy..

(pusto)

a wiec nie ma co dalej robic.
teraz test wlasciwy: czy gramatyka generuje zdania skonczone? tak na prawde, interesujace sa tylko reguly startowe (regul-y, nie regul-a, bo moze ich byc wiele!): jesli wszystkie reguly startowe maja skonczone rozwiniecia, to gramatyka generuje skoczone zdania. patrzac na nasz przypadek - regula @->A zostala usunieta, wiec jest 'bezpieczna', czyli ma skonczone rozwiniecie, czyli wszystkie reguly startowe maja skonczone rozwiniecie, czyli gramatyka ma zdania skonczone.. uff..

inny przypadek:

1: @->aA
2: A->bABC
3: B-> bA
4: C-> c

macierz:

  @ A B C
@ - o - -
A - o o o
B - o - -
C - - - -

badanie-usuwanie.. C jest bezpieczne..

  @ A B
@ - o -
A - o o
B - o -

i.. to koniec. zadna z regul wiecej nie okazuje sie byc bezpieczna. (i rzeczywiscie, reguly A wraz z B zawsze rozwijaja sie na przemian w siebie samych)

teraz test wlasciwy: czy gramatyka generuje zdania skonczone? tak na prawde, interesujace sa tylko reguly startowe (regul-y, nie regul-a, bo moze ich byc wiele!): jesli wszystkie reguly startowe maja skonczone rozwiniecia, to gramatyka generuje skoczone zdania. patrzac na nasz przypadek - regula startowa @->aA nie zostala usunieta, wiec jest niebezpieczna i prowadzi do nieskonczonego, nieograniczonego zapetlenia. czyli gramatyka generuje zdania nieskonczone

ten sam przypadek z 1 regula wiecej

1: @->aA
2: A->bABC
3: B-> bA
4: C-> c
5: B-> bC

macierz:

  @ A B C
@ - o - -
A - o o o
B - o - -
C - - - -
B - - - o

i kolejne eliminacje:

C jest ok

  @ A B
@ - o -
A - o o
B - o -
B - - -

B jest ok

  @ A
@ - o
A - o

i koniec. jak widac, mimo ze dodalismy "wygaszenie" symbolu B, to i tak to nic nie naprawilo -- A sie zawsze zapetla samo ze soba, gramatyka jest caly czas "fuj"..

tonic_ napisał(a)

Mam na przykład sytuację:
@>aB
@>fD
A>cB
A>dE
B>bA
C>eD
D>gE
D>hG
E>aD
G>dH
G>b
H>eG

ja bym to zrobił tak.

mamy tablicę bool v[n]. v[i] == 1 jeśli stan i jest 'zapalony', 0 w przeciwnym wypadku. stan to duża litera.

teraz robimy algo (zwraca true jeśli mamy cykl nieskończony):

bool sprawdz(int v) // v - wierchołek, czyli stan, jego dzieci to jego możliwe rozwinięcia
{
  dla każdego syna (oznaczmy go u)
    jeśli którykolwiek stan z u jest zapalony to zwróć true; (np: stany z przejścia D > AB to A i B)
    zapal wszystkie stany z u
    jeśli sprawdz(u) zwróci true to zwróć true;
    zgaś wszystkie stany z u
  zwróć false;
}

wywołujemy jako:
sprawdz(@);

i mamy liniówkę.

zakładamy na początku, że nie ma przejść typu G > @ (czyli stan G jest zamieniany na nic), czyli jeśli są to je wywalamy. jeśli to było jedyne przejście z danego stanu, to wywalamy ten stan z pozostałych reguł.

to można zrobić liniowo za pomocą kolejki.

na początku do kolejki wstawiamy stan @ (stan pusty).

dopóki kolejka niepusta
  ściągnij stan V
  dla każdego rodzica stanu (czyli przejścia takiego, że prowadzi do V, np: G > AV lub G > aV)
    wytnij stan V z tego przejścia (rodzica)
    jeśli po wycięciu to przejście zostało przejściem pustym (tzn. typu G > @) to
      usuń to przejście
      jeśli wierzchołka poprzedzającego to przejście (np: w przejściu A > BC wierchołek poprzedzający to A) nie ma na kolejce to
        dodaj ten wierzchołek do kolejki

erm.. o ile dobrze wszystko zrozumialem, Twoj algo sprawdza ograniczonosc rozwiniecia, a nie skonczonosc, tzn w przypadku regul

@->A
A->aB
B->aA
A->a

zwroci 'true', a jest to gramatyka o zdaniach skonczonych..

pobawilem sie troche. program ktory ja opisalem znajdziecie tu:

http://pastebin.4programmers.net/3462

przykladowe wejscie:
@>aA
A>aB
B>bBC
B>b
C>cB

przykladowe wejscie:
@>aB
@>fD
A>cB
A>dE
B>bA
C>eD
D>gE
D>hG
E>aD
G>dH
G>b
H>eG

oba zglaszaja ze sa skonczone, czyli poprawnie

disclaimer: nie jest to dzielo sztuki, tylko zostal napisany doslownie tak jak przedstawilem algo.

edit: aha.. program jest linuksiarsko przystosowany do przekierowania wejscia.. np.
~ ./grammar < wejscie.txt
jak wpisywana z palca, to ctrl-d na koniec..

ok, może coś pomieszałem ;p

gramatyki miałem już dawno.

Serdeczne dzięki za pomoc wszystkim!!!! A w szczególności uzytkownikowi quetzalcoatl który zamieścił rozbudowane rozwiazanie i wszystkie szczególy jak poradzic sobie z tym problemem! Pozdrawiam i dzieki raz jeszcze!