[Gramatyki] Zbuduj gramatykę adresu e-mail

[Hubu999]

Cześć,
Mam problem z nastepującym zadaniem:

Załóżmy, że poprawny adres e-mailowy składa się z nastepujących elementów: niepustego znaku identyfikatora złożonego z samych liter (maksymalnie z trzech), znaku "małpy", niepustej nazwy serwera złożonej z samych liter(maksymalnie pięciu), kropki oraz dwuliterowej nazwy domeny. Załóżmy, że alfabet składa się tylko z liter a i b. Poprawnym adresem e-mailowym jest np adres adres aa@bb.ab. Zbuduj gramatykę, która generuje wszystkie poprawne adresy e-mailowe. Określ jej klasę.

Nie mam pomysłu jak ograniczyć tę gramatykę o maksymalnie trzech, lub pięciu liter...

Z góry dziękuję i pozdrawiam!

[leg14]

gramatyk generująca wszystkie niepuste słowa nad alfabetem \(\displaystyle{ \left\{ a,b\right\}}\) o długości maksymalnie 3:
\(\displaystyle{ A \rightarrow L O O ; L \rightarrow a|b, O \rightarrow a|b|\epsilon}\)

[Hubu999]

Rzeczywiście, o tym nie pomyślałem, dzięki. Jeszcze zastanawiam się nad kwestią poprawnego zapisu całego zadania. Czy może być taki?

\(\displaystyle{ S@W.Y}\)
\(\displaystyle{ S \rightarrow A;\ A \rightarrow LOO;\ L \rightarrow a|b,\ O \rightarrow a|b|\epsilon}\)
\(\displaystyle{ W \rightarrow A;\ A \rightarrow LOOOO;\ L \rightarrow a|b,\ O \rightarrow a|b|\epsilon}\)
\(\displaystyle{ Y \rightarrow A;\ A \rightarrow LL;\ L \rightarrow a|b}\)

Czy taki zapis jest formalnie poprawny?

[leg14]

Źle jest.
Przecież w tej gramatyce wyprowadzalne jest słowo \(\displaystyle{ aaaaa@a.aaaaa}\)
Poza tym formalnie potrzebujesz jeszcze aksjomatu gramatyki

hint:

Ukryta treść:    

potrzebujesz trzech różnych symboli nieterminalnych A

[Hubu999]

Ok, więc taki zapis już jest poprawny do zapisania gramatyki?

\(\displaystyle{ S@W.Y}\)
\(\displaystyle{ S \rightarrow A;\ W \rightarrow B;\ Y \rightarrow C}\)
\(\displaystyle{ A \rightarrow LOO;\ B \rightarrow LOOOO;\ C \rightarrow LL}\)
\(\displaystyle{ L \rightarrow a|b,\ O \rightarrow a|b|\epsilon}\)

[leg14]

Tak, ale jeszcze musisz dopisać produkcję \(\displaystyle{ Z \rightarrow S@W.Y}\)
(z definicji każda gramatyka musi mieć tzw. aksjomat gramatyki, czyli symbol początkowy, od którego rozpoczynaszwyprowadzanie słowa)

[Hubu999]

Ok super dziękuję.
Mam jeszcze problem z jednym zadaniem, mianowicie:
Podaj gramatykę bezkontekstową generującą język:

\(\displaystyle{ L=\lbrace a^n b^m:1 \ :1<m<n \rbrace}\)

Próbuje wykonać coś w stylu
\(\displaystyle{ S \rightarrow aaAb:1;\ A \rightarrow ab|aAb}\)

Tylko, że w tym wypadku jedynie mogę wygenerować n o jeden większe od m a nie o dowolną liczbę. Chyba, że w ogole źle zakładam. Czy miałbys może jakiś pomysł na to zadanie?

[leg14]

\(\displaystyle{ S \rightarrow aa Zbb}\)
\(\displaystyle{ Z \rightarrow ab| S| \epsilon}\)

Na razie (powyżej) mamy generowanie słów postaci \(\displaystyle{ a^nb^n}\), gdzie \(\displaystyle{ n>1}\)
Zauważ, że po to wprowadziłem symbol \(\displaystyle{ Z}\) byśmy nie mogli wygenerować \(\displaystyle{ ab}\)

Teraz dodajemy
\(\displaystyle{ W \rightarrow A S}\)
\(\displaystyle{ A \rightarrow aA|a}\)

(W jest aksjomatem)

[Hubu999]

Mam jeszcze problem z dwiema, należy podac gramatykę generującą język:

1. \(\displaystyle{ L=\lbrace w \in \lbrace a,b \rbrace ^* \ w|=3 \rbrace}\)
2. \(\displaystyle{ L=\lbrace w \in \lbrace a,b \rbrace ^* \ :}\) trzecim symbolem słowa jest a \(\displaystyle{ \rbrace}\)

[leg14]

W obu przypadkach L to aksjomat
1.
\(\displaystyle{ L \rightarrow OOO, O \rightarrow a|b}\)
2. (jesli zawsze słowo musi mieć co najmniej 3 litery

\(\displaystyle{ L \rightarrow OOaR, O \rightarrow a|b, R \rightarrow \epsilon|aR|bR}\)
(zauważ, że R produkuje dowolne słowo nad \(\displaystyle{ \left\{ a,b\right\}}\))

2. (jeśli ma zachodzić implikacja: 3 litera istnieje
ightarrow jest równa a)
\(\displaystyle{ L \rightarrow <2 lub 1,0 litery>, <co najmniej3 litery>}\)
\(\displaystyle{ <co najmhniej 3 litery \rightarrow OOaR, O \rightarrow a|b, R \rightarrow \epsilon|aR|bR}\)
\(\displaystyle{ <2 lubv 1,0 litery> \rightarrow \epsilon|ab|aa|bb|ba|a|b}\)