Języki i gramatyki formalne (gramatyki kombinatoryczne)

Witam, chciałbym podszkolić się z zakresu wiedzy o gramatykach (przedmiot "Podstawy Informatyki" na politechnice), niestety nie mam wystarczających materiałów z tego zakresu, a internet jest w tym temacie strasznie ograniczony. Chodzi mi o zadania, ponieważ mam np. wypisać językiem (gramatyką) formalną "Liczbę całkowitą ósemkową ze znakiem" i tu przykłady: -11, +55071, 0, 62.
Albo "Liczba binarna, parzysta, niepodzielna przez 4 i symetryczna względem środka". Nie mam pojęcia jak opisać to zgodnie z gramatyką kombinatoryczną i prosiłbym bardzo o jakieś wprowadzenie i wyjaśnienie co z czym i jak to się je, albo o jakieś pomocne materiały.

Z góry dziękuję!

http://kompilatory.agh.edu.pl/

Dziękuję bardzo za materiał! Widzę, że został porządnie wytłumaczony. Jedyne czego mogę się czepiać to zadań, bo większość są w stylu zrobienia palindromów gramatyką, a na ćwiczeniach dostajemy niestety zadania stricte matematyczne.

Na to niestety nic nie poradzę ;) Ot widać jeden wykładowca kładzie nacisk na X a inny na Y. Ten AGHowy kurs Automatów i Języków Formalnych jest robiony jako wstęp do Teorii Kompilacji, stąd też skupia się mocniej na gramatykach do parsowania symboli, żeby potem wprowadzać w świat Parserów.
Niemniej te twoje zadania wiele się nie różnią, musisz tylko zrozumieć założenia.
Na przykład:
"Liczbę całkowitą ósemkową ze znakiem"

1. Potrzebujemy żeby ciąg zaczynał sie znakiem
2. Liczba ósemkowa więc symbole z zakresu 0-7

S -> +A | -A
A -> BA | B
B -> 0|1|2|3|4|5|6|7

i voila

Analogicznie
"Liczba binarna, parzysta, niepodzielna przez 4 i symetryczna względem środka

1. Liczba binarna więc symbole terminalne 0 i 1
2. Parzysta, więc ostatni symbol musi być 0
3. Niepodzielna przez 4, więc dwa ostatnie symbole nie mogą być 00, co w połączeniu z 2) daje nam że suffix musi być 10 (o ile liczba nie jest jednocyfrowa)
4. Symetyczna względem środka, czyli musimy dodawać z obu stron zawsze takie same symbole

Czyli coś w stylu:

S -> A|B
A -> 01C10
B -> 0|1|010
C -> 0C0 | 1C1 | eps

(może być źle, na kolanie teraz z marszu napisałem :P)