[Gramatyki] Znajdź gramatykę dla języka i udowodnij L=L(G)

MonMonMon
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 22 sty 2015, o 19:35
Płeć: Kobieta
Lokalizacja: Kraków

[Gramatyki] Znajdź gramatykę dla języka i udowodnij L=L(G)

Post autor: MonMonMon »

Witam wszystkich!

Mam problem z rozwiązaniem do końca zadań typu:

Zad: Znajdź gramatykę dla języka:
\(\displaystyle{ L= { a^{2n} , n \ge 0 }}\)
I udowodnij, że:
\(\displaystyle{ L=L(G)}\)

Pamiętam, że stosowaliśmy metodę:
Udowodnij:
1. \(\displaystyle{ L \subset L(G)}\)
2. \(\displaystyle{ L(G) \subset L}\)

Oraz to, że (o ile dobrze pamiętam) podpunkt nr 2 rozwiązywało się za pomocą drzewka, pokazując wszystkie możliwe postaci wygenerowanych przez gramatykę słów.

Nie mam jednak pojęcia, jak się udowadniało w drugą stronę. Przeszukałam już forum, pół internetu oraz wykłady i notatki ale nie mogę tego nigdzie znaleźć. Wszędzie pisze o tym, że jak gramatyka jest "jakaś tam" to wtedy \(\displaystyle{ L=L(G)}\). Możliwe, że chodzi o lemat o pompowaniu, ale nie pamiętam metody dowodu z jego użyciem.

Nie wiem nawet jak nazywa się ta metoda, żeby usprawnić poszukiwania. W dodatku jest mi to niezmiernie potrzebne na "już" a to forum to jedna z moich ostatnich desek ratunku.

Nie proszę o rozwiązanie tego zadania. Chodzi mi o samą metodę, o jakąś wskazówkę gdzie ewentualnie szukać metody którą normalnie się takie zadania rozwiązuje oraz przykładów. Resztę powinnam załapać. Jeśli ktoś cokolwiek wie na ten temat, będę dozgonnie wdzięczna.

Pozdrawiam!
Ostatnio zmieniony 23 sty 2015, o 08:22 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ