[Gramatyki] Czy jest jednoznaczna i regularna

[szymonides]

Cześć!
Rozwiązałem kilka zadań - moglibyście sprawdzić, czy są one poprawnie rozwiązane?

Zadanie 1.
Załóżmy, że mamy gramatykę z symbolem startowym S:
\(\displaystyle{ S \rightarrow aS

S \rightarrow aSb

S \rightarrow SS

S \rightarrow \epsilon}\)

Czy ta gramatyka jest jednoznaczna?
Gramatyka jest jednoznaczna \(\displaystyle{ \Leftrightarrow}\) gdy każde słowo z jej alfabetu można wygenerować za pomocą dokładnie jednego drzewa rozbioru.
Weźmy np. puste słowo \(\displaystyle{ \epsilon}\). Możemy wygenerować je na minimum dwa sposoby:
\(\displaystyle{ S \rightarrow \epsilon}\)
oraz
\(\displaystyle{ S \rightarrow SS \rightarrow \epsilon S \rightarrow \epsilon \epsilon \rightarrow \epsilon}\)
Zatem gramatyka nie jest jednoznaczna.

Zadanie 2
Weźmy gramatykę z symbolem startowym S:
\(\displaystyle{ S \rightarrow aSb

S \rightarrow \epsilon}\)
Czy język generowany przez powyższą gramatykę jest regularny?

Język jest regularny \(\displaystyle{ \Leftrightarrow}\) gdy można go zapisać za pomocą gramatyki regularnej.
Gramatyka jest regularna \(\displaystyle{ \Leftrightarrow}\) gdy każde przejście jest zapisane wg następującej zasady: po lewej stronie przejścia znajduje się dokładnie jeden symbol nieterminalny, a po prawej stronie przejścia dokładnie jeden symbol nieterminalny, a za nim dowolna liczba symboli terminalnych.

Słowa wygenerowane przez powyższą gramatykę to np. "ab", "aaaabbbb", "aaaaaaaaaabbbbbbbbbb"
Powyższa gramatyka tworzy słowa parzystej długości \(\displaystyle{ 2n}\). Pierwsze \(\displaystyle{ n}\) liter to litery "a", a kolejne \(\displaystyle{ n}\) liter to litery "b".
Nie możemy zbudować przejść takich jakich wymaga definicja gramatyki regularnej, bo wyłącznie przejście \(\displaystyle{ S \rightarrow aSb}\) gwarantuje nam utworzenie słów o tej samej liczbie liter "a" w prefiksie i "b" w sufiksie. Zatem gramatyka nie jest regularna.