Skonstruuj gramatyke bezkontekstową generujaca jezyk
\(\displaystyle{ L=\{w \in \{(,)\} ^{*}\ |\ w\text{ jest poprawnym nawiasowaniem}\}}\).
Uwaga: zamiast litery \(\displaystyle{ (}\) użyj \(\displaystyle{ a}\), zas zamiast \(\displaystyle{ )}\) uzyj \(\displaystyle{ b}\).
Odpowiedz:
\(\displaystyle{ S \rightarrow E | aSb |SS}\)
Skad taka odpowiedz? moglby mi ktos to wytlumaczyc?
gramatyka bezkontekstowa jak to ugryzc?
-
- Użytkownik
- Posty: 423
- Rejestracja: 6 paź 2014, o 20:03
- Płeć: Mężczyzna
- Lokalizacja: Torun
- Podziękował: 127 razy
- Pomógł: 2 razy
gramatyka bezkontekstowa jak to ugryzc?
Ostatnio zmieniony 29 maja 2019, o 19:13 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
- Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: gramatyka bezkontekstowa jak to ugryzc?
Słowo puste jest poprawnym nawiasowaniem. Jeśli \(\displaystyle{ S_1}\) i \(\displaystyle{ S_2}\) to poprawne nawiasowania, to \(\displaystyle{ S_1 S_2}\) też jest poprawnym nawiasowaniem. Podobnie jeśli \(\displaystyle{ S}\) jest poprawnym nawiasowaniem, to \(\displaystyle{ (S)}\) także. Pozostaje tylko przekonać się, że każde poprawne nawiasowanie może być otrzymane ze słowa pustego przez ciąg takich przekształceń jak powyżej.