Takie oto zadanie wpadło mi w ręce i nie mam pomysłu jakby je ugryźć, ktoś coś?
Zdefiniować gramatykę generującą napis składający się z następujących 3 znaków: RB_. Przy czym litery są przedzielone znakiem _ oraz Liter R jest 3 razy więcej niż liter B. Przykład prawidłowego napisu: B_R_R_R_R_R_R_B
eazy man, proste jak budowa cepa.
Losujesz liczbę ta wylosowana liczba to = ilość liter B.
Ewentualnie liczysz od 1-N.
Ustawiasz R jako ilość N*3.
Teraz losujesz permutacje bez powtórzeń dla tablicy R+B tych znaków czyli tab = (n*"B" + "R"3N) .
Przelatujesz dla każdej permutacji liczby i dodajesz między znaki _ od 1 do len(tab)-1 inserta robisz w tablicy ewentualnie appendujesz do nowej tablicy raz znak z tego raz _ kończąc i zaczynając od tab.
Nie wiem poco ci takie coś, ale to proste.
S -> A | A_S
A -> B_R_R_R | R_B_R_R | R_R_B_R | R_R_R_B
Coś takiego powinno pyknąć. W każdej produkcji dającej B generujemy jednocześnie 3 R.
Tak opisany (przez OP) język nie jest bezkontekstowy. To co @Shalom napisał daje podzbiór opisanego języka...
@koszalek-opalek: to prawda, ale to co opisałem to jedyna metoda wygenerowania bezkontekstowego podzbioru takiego języka.
koszalek-opalek napisał(a):
Tak opisany (przez OP) język nie jest bezkontekstowy. To co @Shalom napisał daje podzbiór opisanego języka...
Yhm, na przykład: "B_B_B_R_B_R_R_R_R_R_R_R_R_R_R_R" należy do gramatyki, a nijak nie widać jak go uzyskać z tych reguł. Nie mam dowodu, ale zaryzykuje stwierdzenie, że nie da się wygenerować tego języka z języka regularnego (regexa); gdyż te [języki regularne] nie są w stanie zapamiętać i potem odliczyć pewną zadaną (lub, jak tutaj jej wielokrotność) ilość danego znaku.
Na przykład nie da się skonstruować wyrażenia regularnego rozpoznającego czy dowolny ciąg nawiasów jest zbalansowany: "(())" - jeśli dopuszczamy dowolną ilość zagłębień takiego ciągu.
W czym to ma zastosowanie, bo google jakoś nie chce mi odpowiedzieć.
WeiXiao napisał(a):
W czym to ma zastosowanie, bo google jakoś nie chce mi odpowiedzieć.
W informatyce teoretycznej
WeiXiao napisał(a):
W czym to ma zastosowanie, bo google jakoś nie chce mi odpowiedzieć.
W gnębieniu studentów drugiego roku.
lion137 napisał(a):
WeiXiao napisał(a):
W czym to ma zastosowanie, bo google jakoś nie chce mi odpowiedzieć.
W gnębieniu studentów drugiego roku.
Bez przesady. Dzięki temu działają kompilatory, parsery, interpretery, indentery, podświetlacze składni itp. itd...
lion137 napisał(a):
koszalek-opalek napisał(a):
Tak opisany (przez OP) język nie jest bezkontekstowy. To co @Shalom napisał daje podzbiór opisanego języka...
Yhm, na przykład: "B_B_B_R_B_R_R_R_R_R_R_R_R_R_R_R" należy do gramatyki, a nijak nie widać jak go uzyskać z tych reguł. Nie mam dowodu, ale zaryzykuje stwierdzenie, że nie da się wygenerować tego języka z języka regularnego (regexa); gdyż te [języki regularne] nie są w stanie zapamiętać i potem odliczyć pewną zadaną (lub, jak tutaj jej wielokrotność) ilość danego znaku.
Na przykład nie da się skonstruować wyrażenia regularnego rozpoznającego czy dowolny ciąg nawiasów jest zbalansowany: "(())" - jeśli dopuszczamy dowolną ilość zagłębień takiego ciągu.
Przy czym gramatyki bezkontekstowe umieją więcej niż wyrażenia regularne. Ale i tak wspomniane zadanie nie ma rozwiązania w gramatykach bezkontekstowych. Podejrzewam, że wystarczyć może automat ze stodem.