Gramatyka bezkontekstowa Filip: Witam, czy jest tutaj ktos kto ma pojecie na temat gramatyki bezkontekstowej?

Filip: Mam taka gramatyke bezkontekstowa S→aSa|bSb|a|b|ε I przykladowo dla n = 6 dostaje {a, b, aaa, aba, bab, bbb} ?

Pytający: S→aSa|bSb|a|b|ε nie jest gramatyką (aczkolwiek można się domyślić, o jakiej gramatyce mówisz). Jednak czym jest to "n"?

Filip: n to liczba lancuchow. Pelna tresc polecenia brzmi: Napisz program, ktory wypisze na ekranie n lancuchow z jezyka opisanego za pomoca gramatyki bezkontekstowej: S→aSa|bSb|a|b|ε Program powinien wyswietlac opis gramatyki bezkontekstowej, a wypisywane lancuchy powinny byc uporzadkowane w postaci kanonicznej Odchodzac od napisania prgoramu, narazie mam sam problem ze zrozumieniem jak tworzyc te lancuchy

Filip: Okej, jak rozumiem... Zaczynam od S i moge je zamienic na aSa lub bSb lub a lub b lub lancuch pusty ktory przerywa generowanie. na przyklad zamieniam na aSa i tutaj znowu powtarzam czynnosc. Wybieram dowolny lancuch, jednak co sie stanie jesli za S wstaiw a lub b? Otrzymam wtedy aab lub aba i juz nie mam tutaj S, wiec koncze generowanie?

Filip: No chyba ze ide od "lewej do prawej" czyli Jak zamienie S na bSb to pozniej bSb bede mogl tylko zamienic na a lub b lub lanuch pusty?

Pytający: Nie bardzo wiem, co znaczy tutaj "uporzadkowane w postaci kanonicznej". Generalnie każde S możesz zamienić na aSa albo bSb albo a albo b albo ε. Znaczy jeśli zaczynasz od S to w "pierwszej iteracji" możesz otrzymać: • aSa • bSb • a // nie ma co tu więcej zamieniać, znaczy jest to słowo generowane przez tę gramatykę • b // słowo • ε // słowo W "drugiej iteracji" zaczynasz z aSa i bSb i możesz otrzymać: // aSa: • aaSaa • abSba • aaa // słowo • aba // słowo • aa // słowo // bSb: • baSab • bbSbb • bab // słowo • bbb // słowo • bb // słowo I tak dalej. Generalnie ta gramatyka generuje wszystkie palindromy nad alfabetem {a, b}. Nie wiem, które 6 masz tu wypisać, może {ε, a, b, aa, bb, aaa} (ale to strzał).

Husten Saft: Klusek jest taki aforyzm G Eliota Blogoslawiony niech bedzie czlowiek ktory nie majac nic do powiedzenia nie dostarcza tego dowodu w slowach

Filip: W postaci kanonicznej to znaczy uporzadkowac rosnaco/malejaco wzgledem dlugosci lancucha, a lancuchy o tej samej dlugosci alfabetycznie. Zapewne kolejne utworzeone lancuchy bede wrzucac do wektora, i przydaloby sie napisac funkcje sortujaca, ktora sortuje zarowno rosnaco/malejaca, a nastepnie alfabetycznie te lancuchy, ktore trzeba

Filip: Taki pomysl od razu przyszedl mi na mysl, jeszcze nie podchdozilem do tego problemu w kodzie. Naracie chcialem zrozumiec sama koncepcje

Filip: @Pytajacy... chyba rozgryzlem patent na jakies zasadzie to dziala 1) dla aSa mam {aaa, aa, aba} dla bSb mam {bbb, bb, bab} 2) dla aaSaa mam {aaaaa, aaaa, aabaa} − czyli dodaje po jedno a z przodu i z tylu od lanuchow aSa dla abSba mam {abba, abbba, ababa} − czyli dodaje po jedno a z prozdu i z tylu od lancuchow bSb 2.1) dla baSab mam {baaab, baab, babab} − czyli dodaje po jedno b z przodu i z tylu lancuchow aSa dla bbSbb mam {bbbbb, bbabb, bbbb} − czyli dodaje po jedno b z przodu i z tylu lancuchow bSb No i jak przejde taki jeden cykl, zwiekszam liczbe dodawanych liter z przodu i z tylu o 1 Napisalem w kodzie to tak, prototyp, nie wyglada zbyt ladnie: char aSa[3][4] = { {'a', 'a', 'a', '\0'}, {'a', 'b', 'a', '\0'}, {'a', 'a', '\0', 'c'} }; char bSb[3][4] = { {'b', 'b', 'b', '\0'}, {'b', 'a', 'b', '\0'}, {'b', 'b', '\0', 'c'} }; int a = 5; int k = 1; while (a > 0) { for (int i = 0; i < 3; i++) { for (int i = 0; i < k; i++) { printf("a"); } printf("%s", aSa[i]); for (int i = 0; i < k; i++) { printf("a"); } printf("\n"); } for (int i = 0; i < 3; i++) { for (int i = 0; i < k; i++) { printf("a"); } printf("%s", bSb[i]); for (int i = 0; i < k; i++) { printf("a"); } printf("\n"); } for (int i = 0; i < 3; i++) { for (int i = 0; i < k; i++) { printf("b"); } printf("%s", aSa[i]); for (int i = 0; i < k; i++) { printf("b"); } printf("\n"); } for (int i = 0; i < 3; i++) { for (int i = 0; i < k; i++) { printf("b"); } printf("%s", bSb[i]); for (int i = 0; i < k; i++) { printf("b"); } printf("\n"); } printf("\n"); k++; a−−; }

Filip: Output tego programu jest taki... wyglada na to ze potworzyly sie palindromy aaaaa aabaa aaaa abbba ababa abba baaab babab baab bbbbb bbabb bbbb aaaaaaa aaabaaa aaaaaa aabbbaa aababaa aabbaa bbaaabb bbababb bbaabb bbbbbbb bbbabbb bbbbbb aaaaaaaaa aaaabaaaa aaaaaaaa aaabbbaaa aaababaaa aaabbaaa bbbaaabbb bbbababbb bbbaabbb bbbbbbbbb bbbbabbbb bbbbbbbb

Filip: Udalo mi sie napisac dzialajacy kod, wyswietlajacy n palindromow... #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> int cmp(const void* a, const void* b) { char* f = (char*)a; char* s = (char*)b; return strlen(f) − strlen(s); } int main() { int n; scanf("%d", &n); //char aSa[3][4] = { {'a', 'a', 'a', '\0'}, {'a', 'b', 'a', '\0'}, {'a', 'a', '\0', 'c'} }; //char bSb[3][4] = { {'b', 'b', 'b', '\0'}, {'b', 'a', 'b', '\0'}, {'b', 'b', '\0', 'c'} }; char** aSa; aSa = malloc(3 * sizeof(char*)); aSa[0] = malloc(4 * sizeof(char)); aSa[0] = "aaa"; aSa[1] = malloc(4 * sizeof(char)); aSa[1] = "aba"; aSa[2] = malloc(3 * sizeof(char)); aSa[2] = "aa"; char** bSb; bSb = malloc(3 * sizeof(char*)); bSb[0] = malloc(4 * sizeof(char)); bSb[0] = "bbb"; bSb[1] = malloc(4 * sizeof(char)); bSb[1] = "bab"; bSb[2] = malloc(3 * sizeof(char)); bSb[2] = "bb"; char t[1000][1000]; int m = 0; int a = 10; int k = 1; while (a > 0) { for (int i = 0; i < 3; i++) { char* c = malloc(sizeof(char) * 1000 + 2 * k); for (int j = 0; j < k; j++) { c[j] = 'a'; } strcpy(c + k, aSa[i]); char* p = malloc(k * sizeof(char) + 1); for (int i = 0; i < k; i++) { p[i] = 'a'; } p[k] = '\0'; strcat(c + k + strlen(aSa[i]), p); strcpy(t[m++], c); //printf("%d\n", strlen(c)); /* for (int i = 0; i < k; i++) { printf("a"); } printf("%s", aSa[i]); for (int i = 0; i < k; i++) { printf("a"); } //printf() */ } for (int i = 0; i < 3; i++) { char* c = malloc(sizeof(char) * 1000 + 2 * k); for (int j = 0; j < k; j++) { c[j] = 'a'; } strcpy(c + k, bSb[i]); char* p = malloc(k * sizeof(char) + 1); for (int i = 0; i < k; i++) { p[i] = 'a'; } p[k] = '\0'; strcat(c + k + strlen(bSb[i]), p); strcpy(t[m++], c); //printf("%d\n", strlen(c)); } for (int i = 0; i < 3; i++) { char* c = malloc(sizeof(char) * 1000 + 2 * k); for (int j = 0; j < k; j++) { c[j] = 'b'; } strcpy(c + k, aSa[i]); char* p = malloc(k * sizeof(char) + 1); for (int i = 0; i < k; i++) { p[i] = 'b'; } p[k] = '\0'; strcat(c + k + strlen(aSa[i]), p); strcpy(t[m++], c); //printf("%d\n", strlen(c)); } for (int i = 0; i < 3; i++) { char* c = malloc(sizeof(char) * 1000 + 2 * k); for (int j = 0; j < k; j++) { c[j] = 'b'; } strcpy(c + k, bSb[i]); char* p = malloc(k * sizeof(char) + 1); for (int i = 0; i < k; i++) { p[i] = 'b'; } p[k] = '\0'; strcat(c + k + strlen(bSb[i]), p); strcpy(t[m++], c); //printf("%d\n", strlen(c)); } k++; a−−; } strcpy(t[m++], ""); strcpy(t[m++], "a"); strcpy(t[m++], "b"); for (int i = 0; i < 3; i++) { strcpy(t[m++], aSa[i]); strcpy(t[m++], bSb[i]); } qsort(t, m, 1000, cmp); printf("["); for (int i = 0; i < n; i++) { if (i != n − 1) { printf("%s, ", t[i]); } else { printf("%s]", t[i]); } } }

Pytający: Zauważ, że: • masz jedynie dwie litery w alfabecie, • palindrom jest jednoznacznie zdefiniowany poprzez prefix + ewentualną środkową literę (gdy długość palindromu jest nieparzysta). Stąd przyszło mi na myśl, żeby palindromy generować z binarnej postaci kolejnych liczb całkowitych danej długości. Przykładowo: • palindromy długości 0: // (binarnie prefix + ewentualna środkowa) → (binarnie całość) → (literalnie całość) ε → ε → ε • palindromy długości 1: // nieparzysta długość, więc nie powielasz ostatniej cyfry / litery 0 → 0 → a 1 → 1 → b • palindromy długości 2: 0 → 00 → aa 1 → 11 → bb • palindromy długości 3: // nieparzysta długość, więc nie powielasz ostatniej cyfry / litery 00 → 000 → aaa 01 → 010 → aba 10 → 101 → bab 11 → 111 → bbb • palindromy długości 4: 00 → 0000 → aaaa 01 → 0110 → abba 10 → 1001 → baab 11 → 1111 → bbbb itd. Takich palindromów długości d = 2k jest 2^k. Takich palindromów długości d = 2k + 1 jest 2^k+1. Stąd takowa implementacja: https://ideone.com/q4zNxI

Pytający: + z wypisaniem tych "przejść": https://ideone.com/vSuXct

Filip: Pytajacy, dziekuje ci za kod, kod ktory napisalem powyzej jest bledny, poniewaz dla lancucha o dlugosci i tworzy tylko 4 palindromy. Po przeanalizowaniu tego co napisales, zgadzam sie z toba, ze dla parzystych dostaje kolejno o dlugosci kolejnych lancuchow grupujac na dlugosci parzyste/nieparzyste bedzie rosnac wykladniczo, natomiast mam prosbe, moglbys zerknac w moj kod i poradzic mi, dlaczego maksymalna liczba palindromow, ktora moge wypisac wynosi 509? Bylbym wdzieczny Podrzucam kod, wedlug mnie jest to spowodowane zbyt duzym zajeciem pamieci przez program https://pastebin.com/idW0XFmX

Pytający: Nigdzie podczas generowania palindromów nie uwzględniasz wejściowego "n", pętlę (linia 53.) wykonujesz zawsze 6 razy. 2*∑_j=0⁵(2^j+2) + 5 = 509

Filip: No wlasnie jak juz chce 7 iteracji petli program sie crashuje

Filip: Tak wlasciwie jak uzaleznic te petle zewnetrzna od wejsciowego n?

Pytający: Nic dziwnego, że się crashuje skoro robisz rzeczy typu: char temp[500][32]; czy char* c = malloc(sizeof(char) * 1000 + 2 * k); jakieś uzasadnienie skąd te liczby czy "tak o, na oko"? A jak uzależnić od n? Analogicznie jak u mnie: na starcie przecież wiesz, ile jest palindromów danej długości i wiesz, jaką długość obecnie generujesz. A jeśli chcesz wszystkie wygenerowane palindromy przechowywać w pamięci (a nie np. jedynie wypisywać na bieżąco), to też można wyliczyć na podstawie którego wcześniej wygenerowanego palindromu należy generować kolejny. Nie trzeba jakoś oddzielnie pamiętać parzystych / nieparzystych.

Filip: Tak, wlasnie probuje teraz zminimalizowac zajecie pamieci

Filip: A te liczby to tak na oko wzialem, to sie zgadza