[Gramatyki] Znajdź gramatykę dla języka i udowodnij L=L(G)
: 22 sty 2015, o 19:59
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!
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!