Matematyka.pl

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?

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.