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!
[Gramatyki] Gramatyka bezkontekstowa - konkretny przykład
[Gramatyki] Gramatyka bezkontekstowa - konkretny przykład
Dostałem zadanie aby: napisać program który wypisze na ekranie \(\displaystyle{ n}\) łańcuchów z języka opisanego za pomocą gramatyki bezkontekstowej:
Z zaprogramowaniem nie będzie problemu, ale chciałbym aby ktoś wyjaśnił mi działanie tej gramatyki. Z góry wielkie dzięki!
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.
Powód: Poprawa wiadomości.
-
lukequaint
- Użytkownik
- Posty: 219
- Rejestracja: 5 maja 2010, o 18:27
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 1 raz
- Pomógł: 75 razy
[Gramatyki] Gramatyka bezkontekstowa - konkretny przykład
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}\)
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}\)