gramatyka bezkontekstowa Filip: Witam, mam taki jezyk z gramatyki bezkontekstowej S→A1B A→0A|ε B→0B|1B|ε Czy dobrze mysle, ze to bedzie mi dla lancucha dlugosci n generowalo wszystkie kombinacje o tej dlugosci nad alfabetem {0, 1}? Czyli: 1) 1 2) 01, 10, 11 3) 001, 010, 100, 110, 101, 011, 111 itd... Ogolny wzory na liczbe takich lancuchow o dlugosci n to bedzie 2ⁿ − 1?

Pytający: > Czy dobrze mysle, ze to bedzie mi dla lancucha dlugosci n generowalo wszystkie kombinacje o tej dlugosci nad alfabetem {0, 1}? No nie, łańcuchy zawierające same zera nie należą do języka generowanego przez tę gramatykę (łańcuch pusty też nie). Ale musiałeś sam to zauważyć, bo reszta się zgadza.

Filip: Tak, racja tu o tym nie wspomnialem. Masz pomysl jak generowac kolejne lanuchy? Narazie jedynie wpadlem na pomysl, aby brac wygenerowane lancuchy na miejscu i − 1 a nastepnie do kazdego z nich dodawac na poczatku 0, albo na koncu 0 lub 1. Jednak takie generowanie sprawia problem, ze tworza mi sie duplikaty, a nawet po 3/4 takie same lancuchy, chcialbym to wyeliminowac. Przykladowo moim sposobem generuje z lancuchow {01, 10, 11} 1) Dla 01 dostaje: 001, 010, 011 2) Dla 10 dostaje: 010, 100, 101 2) Dla 11 dostaje: 011, 110, 111 Jak widac w tym sposobie jest zle to, ze dostaje dla 01 oraz 11 taki sam lancuch − 011. Problem sie nasila jezeli bedziemy generowac kolejne lanuchy o wiekszej dlugosci

Pytający: W sensie jak to zrobić w programie? Ano po kolei generujesz wszystkie łańcuchy binarne danej długości z pominięciem tego złożonego z samych zer. A jeśli pytasz jak generować łańcuchy długości (n+1) z łańcuchów długości n, to niech: • a_n[i] będzie i−tym łańuchem długości n wedle kolejności leksykograficznej, • x | y to konkatenacja x oraz y, wtedy: • a_n+1[0] = 0 | a_n[0], • a_n+1[2i + 1] = a_n[i] | 0 dla 0 ≤ i < 2ⁿ − 1, • a_n+1[2i + 2] = a_n[i] | 1 dla 0 ≤ i < 2ⁿ − 1. Startujesz rzecz jasna od a₁[0] = 1.

Filip: Hmm no tak, jednak analizujac twoj algorytm nie dojde do tego co samego na co natrafilem? Ze dla lancucha o dlugosc n niektre wygenerowane lancuchy beda sie powtarzac Przeanalizujmy twoj algorytm Lancuchy o dlugosci 2 tworzone z lancucha o dlugosci 1 {"01", "10", "11"} Lancuchy o dlugosci 3 tworzone z lancuchow o dlugosci 2 {"001", "010", "100", "110", "011", "101", "111"} Lancuchy o dlugosci 4 tworzone z lancuchow o dlugosci 3 {"0001", "0010", "0100", "1000", "1100", "0110", "1010", "1110", "0011", "0101", "1001", "1101", "011", "1011", "1111"} Okej, dopiero po przeanalizowaniu twojego algorytmu juz widze, ze eliminuje on mozliwosc wystapienia tego samego lancucha kilka razy. Dzieki!

Filip: Nasuwa sie pytanie jak to zapisac optymalnie w kodzie, wiemy ile kolejnych lancuchow bedzie, wiec moze jakas dynamiczna alkokacja + realloc()?

Pytający: Standardowo: chcesz zapisać wszystkie wygenerowane łańcuchy w pamięci czy jedynie robić coś z każdym kolejnym na bieżąco podczas generacji (w sensie bez zapisywania)?

Filip: Chce miec n wygenerowanych lancuchow zapisanych w pamieci, poniewaz pozniej bede musial posortowac wygenerowane lancuchy

Pytający: Nie musisz ich sortować, przecież w moim wpisie z 22:28 są już posortowane (wcześniej nie zwróciłem uwagi, że o 22:41 wypisujesz je w innej kolejności niż przeze mnie podana).

Filip: Racja, jednak narazie co zrobilem wyglada mniej wiecej tak, znowu mam ten sam problem, z tym ze genereuje nadmierna ilosc palindrom i na biezaca sprawdzam kiedy moj index bedzie rowny n. Wtedy koncze dzialanie programu. No i maksymalna ilosc palindromow ktora moge wygenerowac to 2¹³ Podrzucam kod: https://pastebin.com/pqStJSGJ

Pytający: Palindromów mówisz? Znowu zaczynasz od magicznych liczb... jak dla mnie łatwiej od razu robić jak trzeba niźli później przerabiać. Podrzucam "przeróbkę": https://ideone.com/6y5oYH

Filip: Juz mi sie powoli w glowiee przewraca od tej gramatyki, to dlatego ze niedawno robilem palindromy, dzieki za kod