Dostałem zadanie aby: napisać program który wypisze na ekranie \(\displaystyle{ n}\) łańcuchów z języka opisanego za pomocą gramatyki bezkontekstowej: S->AA|0 A->S|1.
Z zaprogramowaniem nie będzie problemu, ale chciałbym aby ktoś wyjaśnił mi działanie tej gramatyki. Z góry wielkie dzięki!
Ostatnio zmieniony 12 gru 2015, o 09:17 przez Afish, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.
Co masz na myśli, pisząć "działanie"? Jakie słowa ona generuje?
Z \(\displaystyle{ S}\) możemy wyprowadzić \(\displaystyle{ AA}\) lub \(\displaystyle{ 0}\), a z \(\displaystyle{ A}\) - \(\displaystyle{ S}\) albo \(\displaystyle{ 1}\).
Czyli gramatyka \(\displaystyle{ S \rightarrow AA|0\\
A \rightarrow S | 1}\)
generuje np. \(\displaystyle{ 1110}\), \(\displaystyle{ 11}\), \(\displaystyle{ 0}\) oraz \(\displaystyle{ 11111111}\).
Wyprowadzenie \(\displaystyle{ 1110}\) (zakładając, że \(\displaystyle{ S}\) to symbol startowy): \(\displaystyle{ S \xrightarrow{S \rightarrow AA} AA \xrightarrow{A \rightarrow S} AS \xrightarrow{S \rightarrow AA} AAA \xrightarrow{A \rightarrow S} AAS \xrightarrow{S \rightarrow AA} AAAA \xrightarrow{A \rightarrow S} AAAS \xrightarrow{S \rightarrow 0} AAA0 \xrightarrow{A \rightarrow 1} AA10 \xrightarrow{A \rightarrow 1} A110 \xrightarrow{A \rightarrow 1} 1110}\)