[C] Wypisz łańcuchy z języka gramatyki bezkontekstowej

[Rooster]

Witam!
Chcialbym zapytac o pomoc w zwiazku z ponizszym zadaniem:
"Napisac program, ktory wypisze na ekranie n lancuchow z jezyka opisanego za pomoca gramatyki bezkontekstowej;"
Gramatyka wyglada nastepujaco:
\(\displaystyle{ S \rightarrow aSb|\epsilon}\)

Lancuchy maja byc uporzadkowane w postaci kanonicznej.

Chodzi mi przede wszystkim o jakies mniej formalne wytlumaczenie tego. Z gory dziekuje za wskazowki. Pozdrawiam

[Kartezjusz]

\(\displaystyle{ aSb}\) oznacza,że musisz rozkładać symetrycznie względem jakiegoś środka \(\displaystyle{ a,b}\)
z lewej są \(\displaystyle{ a}\), z prawej są \(\displaystyle{ b}\) i musi ich być tyle samo. po kreskach mamy jakie pojedyńcze słowa są jeszcze dopuszczone. Oprócz tych dopuszczone jest słowo puste.

[Gouranga]

\(\displaystyle{ S \rightarrow aSb|\epsilon}\)
oznacza, że zaczynasz od \(\displaystyle{ S}\) i możesz zamienić \(\displaystyle{ S}\) na \(\displaystyle{ aSb}\), w tym łańcuchu który powstał możesz znów \(\displaystyle{ S}\) zamienić na \(\displaystyle{ aSb}\) uzyskując \(\displaystyle{ aaSbb}\) itd., w każdej chwili możesz też zamienić \(\displaystyle{ S}\) na słowo puste czyli zakończyć generowanie

[Rooster]

Dziękuję bardzo za odpowiedzi.

Czyli innymi słowy, gdyby program miał wywołać 3 łańcuchy mogłoby to wyglądać następująco:
\(\displaystyle{ S}\)
\(\displaystyle{ aSb}\)
\(\displaystyle{ aaSbb}\)

Aczkolwiek równie dobrze program od razu mógłby zamiast S dostać \(\displaystyle{ \epsilon}\)?

Mam na myśli ten element losowości tutaj. Niezależnie od podanej ilości łańcuchów program może zostać zakończony wcześniej, jeśli S zostanie zamienione na \(\displaystyle{ \epsilon}\)?

[Gouranga]

nie
nie możesz wyświetlać \(\displaystyle{ S}\), będziesz miał łańcuchy postaci
\(\displaystyle{ \\
ab\\
aabb\\
aaabbb}\)
gdzie pierwszy łańcuch jest pusty czyli przejście z samego \(\displaystyle{ S}\) na łańcuch pusty
\(\displaystyle{ S}\) to tak jakby wzór w miejsce którego możesz wstawić inny układ znaków natomiast wyświetlać możesz tylko terminale czyli w przypadku tej gramatyki \(\displaystyle{ a,b,\epsilon}\)

[Rooster]

Dziękuję za odpowiedź.

W każdym razie \(\displaystyle{ \epsilon}\) może się tam pojawić losowo w którymkolwiek momencie?

Jeżeli pojawiłoby się coś takiego:
\(\displaystyle{ aaa \epsilon bbb}\)
Oznacza to koniec generowania? Czy dopiero w momencie gdy wszystkie pary \(\displaystyle{ ab}\) zostałyby zamienione na puste znaki?

Jeżeli programowi zostałoby zadane wygenerowanie 30 łańcuchów to mógłby on zakończyć swoje działanie wcześniej, jeżeli dojdzie do momentu, gdzie są same znaki puste?

[Gouranga]

nie do końca chyba rozumiesz istotę gramatyki
masz ten opis
\(\displaystyle{ S \rightarrow aSb | \epsilon}\)

czytasz to w taki sposób: Zaczynając od \(\displaystyle{ S}\) można zamienić wzór \(\displaystyle{ S}\) na \(\displaystyle{ aSb}\) lub na znak pusty.
Natomiast słowo (łańcuch) powstaje gotowy dopiero gdy nie ma w nim już tego \(\displaystyle{ S}\)
to znaczy, że generując 30 pierwszych wyrazów otrzymasz
\(\displaystyle{ \epsilon\\
a\epsilon b\\
aa\epsilon bb\\
aaa\epsilon bbb\\
\underbrace{a\ldots a}_{29} \epsilon \underbrace{b\ldots b}_{29}}\)

gdzie oczywiście \(\displaystyle{ \epsilon}\) nie wyświetlasz

jeśli ci to ułatwi zrozumienie to np. taka gramatyka:
\(\displaystyle{ S \rightarrow aS | a}\)
wygeneruje ci dowolnie długi ciąg złożony z liter 'a' nie dając możliwości wpisania pustego słowa (bo najkrótsze daje przejście z S od razu na a)

[Rooster]

Czyli równie dobrze mogłoby wystąpić:


\(\displaystyle{ \epsilon\\ a\epsilon b\\ aa\epsilon bb\\ aaa\epsilon bbb\\ \underbrace{a\ldots a}_{17}
\underbrace{\epsilon \dots \epsilon}_{13} \underbrace{b\ldots b}_{17}}\)

I inne płynące z tego pytania... Czy dajmy na to gramatyka typu:
\(\displaystyle{ S \rightarrow A0B}\)
\(\displaystyle{ A \rightarrow 0A|E}\)
\(\displaystyle{ B \rightarrow 0B|1B|E}\)

A w zasadzie generowanie jej łancuchów... Mogłoby zostać przerwane zanim pojawiłoby się ich dajmy na to 30? Z racji na pojawienie się samych \(\displaystyle{ 0, 1}\) i \(\displaystyle{ \epsilon}\)?

[Gouranga]

nie może być więcej niż jeden \(\displaystyle{ \epsilon}\) bo nie ma przejścia na łańcuch zawierający \(\displaystyle{ \epsilon}\) i inny wzór

a co do tej gramatyki:
\(\displaystyle{ S \rightarrow A0B\\
A \rightarrow 0A|E\\
B \rightarrow 0B|1B|E}\)

z \(\displaystyle{ S}\) przechodzimy na \(\displaystyle{ A0B}\), z \(\displaystyle{ A}\) możemy wygenerować ciąg zer dowolnej długości zakończony literą \(\displaystyle{ E}\), z \(\displaystyle{ B}\) dowolny ciag zer i jedynek zakończony \(\displaystyle{ E}\) więc słowo wygenerowane tą gramatyką wygląda mniej więcej tak:
\(\displaystyle{ \underbrace{0 \ldots 0E}_{generowane z A} 0 \underbrace{(0+1)^*E}_{generowane z B}}\)
a minimalne to \(\displaystyle{ E0E}\)
czy też bardziej formalnie
\(\displaystyle{ 0^*E0(0+1)^*E}\)
gdzie czytasz to jako:
\(\displaystyle{ 0^* -}\) ciag dowolnej długości uwzględniając ciag pusty złożony z zer
\(\displaystyle{ (0+1)^* -}\) ciąg dowolnej długości uwzględniając pusty złożony z zer i jedynek

to co napisałem to wyrażenia regularne opisujące gramatyki, możesz pogooglować jak chcesz

[xsqaz]

Dołączę się do tematu.
Co gdy mamy taką gramatykę bezkontekstową : \(\displaystyle{ S \rightarrow AS|0}\)
\(\displaystyle{ A \rightarrow AS|1}\)
Czy łańcuchy z języka opisanego przez tą gramatykę będą postaci: 0, 1, 01, 10, 010, 101, 0101, 1010 itd ?

[Gouranga]

będą to dowolne ciągi zer i jedynek zaczynające się od 1 i kończące na 0
bo jakkolwiek byś nie przechodził to zawsze po prawej zostaje ci S z którego musisz zakończyć terminalem 0 a po lewej A które musisz zakończyć terminalem 1, między to możesz wstawiać dowolne kombinacje A i S

[xsqaz]

Dzięki wielkie

[gramatyka]

Witam podepne się pod temat. Mając dana gramatyke:
\(\displaystyle{ S \rightarrow aSb|aSb|a|b|\epsilon}\)
Czy dobrze rozumiem i pierwsze dajmy na to 10 wyrazów będzie przedstawiac się nastepujaco:
\(\displaystyle{ ab}\)
\(\displaystyle{ aabb}\)
\(\displaystyle{ aaabb}\)
\(\displaystyle{ aabbb}\)
\(\displaystyle{ aabb}\)
\(\displaystyle{ aabb}\)
\(\displaystyle{ aaabbb}\)
\(\displaystyle{ aaaabbb}\)
\(\displaystyle{ aaabbbb}\)
\(\displaystyle{ aaabbb}\)

[Gouranga]

gramatyka, \(\displaystyle{ S \rightarrow aSb|aSb|a|b|\epsilon}\) nie ma sensu, dajesz dwie identyczne możliwości przejścia, popraw bo chyba coś tu źle przepisujesz

[gramatyka]

Sprawdziłem uważnie i nie ma żadnego błędu. Dokladnie taką gramatykę mam podaną i musze napisac program który wypisze n wyrazów z jezyka opisanego za pomocą danej gramatyki.