Sld 10.1. Elementy języków formalnych
Sld 10.2. Języki formalne
Językiem nazywa się niepusty, skończony zbiór różnych słów nad danym alfabetem. Znaczenia tych słów tworzą semantykę języka, a reguły ich używania stanowią składnię języka.
Na słowach określa się operację złożenia (dostawienia, zetknięcia, konkatenacji).
Złożeniem słów Ai i Aj jest słowo Ak powstałe przez zetknięcie ze sobą łańcuchów znaków stanowiących te słowa w taki sposób, że słowo Ai, jest wpisane z lewej strony, a słowo Aj z prawej, przy czym n(Ak) = ni(Ai) + nj(Aj). Operację złożenia zapisuje się przy użyciu znaku kółeczka ,, �", kwadracika "?", znaku "&", znaku dodawania " + ", stosowane są także nawiasy ostre.
Na przykład, dla słów Ai = zkd i Aj = abcde

Ak = Ai� A j = Ai? A j = Ai& A j = ?Ai Aj? = zkdabcde

Szczególnym słowem jest jedyne słowo o długości 0. Jest to słowo puste, czyli funkcja pusta. Oznaczamy je przez ?, ? = A0.
Sld 10.3. Elementy języków formalnych 2
Szczególnym słowem jest jedyne słowo o długości 0.
Jest to słowo puste, czyli funkcja pusta. Oznaczamy je przez ?, ? = A0.

Zbiór wszystkich słów n-literowych nad A (słów o długości n) pokrywa się więc ze zbiorem An wszystkich funkcji z n do A.

Zbiór wszystkich słów nad A oznaczamy przez A*:


Zbiór słów niepustych oznaczamy przez A+ :

A + = A* / ?.

Sld 10.4. Gramatyki formalne 
Gramatyka formalna to czwórka
G = ( V, T , P, S ),
gdzie
V - zbiór zmiennych (symboli nieterminalnych, niekońcowych)
T - zbiór symboli końcowych (terminalnych),
P
skończony zbiór produkcji, każda produkcja ma postać
?? ?, gdzie ?, ? są lańczuchami symboli danej gramatyki, przy czym ? ? ? , ?, ? ? V*, V* = (V? T)* ; Vn=Vn-1V; V0=? ,
S - specjalna zmienna, zwana symbolem początkowym
Produkcja - to reguły więżące ze sobą zmienne.
Sld. 10. 5. Hierarchia Chomsky'ego
Hierarchia Chomsky'ego składa się z czterech poziomów:

0. Języki typu zero, czyli rekurencyjnie przeliczalne.
1. Języki typu jeden, czyli kontekstowe (monotoniczne).
2. Języki typu dwa, czyli bezkontekstowe.
3. Języki typu trzy, czyli regularne.
Sld. 10.6. Gramatyki formalne typu 0 i 1
0. Gramatyki typu zero, czyli rekurencyjnie przeliczalne.
Każda produkcja ma postać ? ? ?, gdzie ?, ? są dowolnymi łańcuchami
symboli danej gramatyki. Niema ograniczeń na produkcji. Gramatyki te zwane są jako gramatyki nieograniczone lub struktury frazowe. Dla dowolnego języka naturalnego można zbudować model matematyczny jaki stoguje się taką gramatyką.

1. Gramatyki typu jeden, czyli kontekstowe (monotoniczne).
Jeżeli ??????? - na gramatyki struktur frazowych nałożony warunek, że ? ma być co najmniej tak długie, jak ?. Wtedy gramatykę tę nazywamy kontekstową, a generowany przez nią język językiem kontekstowym (skróty: GK i JK). Produced o tej postaci wyglądają jak produkcje bezkontekstowe, ale pozwalają na zastąpienie zmiennej ? łańcuchem � tylko w "kontekście" .

Sld. 10.7. Gramatyki formalne typu 2 i 3
2. Gramatyki typu dwa, czyli bezkontekstowe.
Słowo ? utworzone jest z jednego symboliu ? ? V . Skróty: GBK i JBK.

3. Gramatyki typu trzy, czyli regularne.
Słowo ? utworzone jest z jednego symboliu ? ? V ,
�? TV lub �? T. Prawi części produkcji są utworzone z jednego końcowego sumboliu i jednego niekóncowego lub jednego końcowego.

Sld. 10.8. Wyprowadzenia i języki
Zdefiniujemy formalnie język generowany przez gramatykę G = (V, T, P, S). W tym celu wprowadzamy notację do reprezentowania wyprowadzeń. Definiujemy dwie relacje ? i ?* pomiędzy łańcuchami z (V? T)*. Jeśli A � B jest produkcją z P, a ? i ? są dowolnymi łańcuchami z (V? T)*, to ?A? ? ?B?. Mówimy, że produkcja A�B zastosowana do łańcucha ?A? daje w wyniku ?B?, lub że ?B? jest bezpośrednio wyprowadzalny z ?A ? w gramatyce G. Dwa łańcuchy są związane relacją ? dokładnie wtedy, gdy drugi z nich możni otrzymać z pierwszego poprzez zastosowanie jakiejś produkcji.
Przypuśćmy, że ?1, ?2 ,..., ?m są łańcuchami z (V? T)*, m ? 1, oraz
?1 ??2, ?2??3, ..., ?m-1 ? ?m - ?1 ?* ?m
Wtedy piszemy ?1 ?* ?m i mówimy, że ?m jest wyprowadzalny z ?1 w gramatyce G. Sformułowanie alternatywne: ? ?* � jeśli � daje się otrzymać z a w wyniku zastosowania zera lub więcej produkcji z P.
Język generowany przez gramatykę G to
L(G) = {w|w należy do T* i S ?* w}.
Łańcuch w należy do L(G), jeśli spełnione są dwa następujące] warunki:
1. w składa się wyłącznie z symboli końcowych.
2. w jest wyprowadzalny z S.


Sld. 10.9. Gramatyki typu dwa (bezkontekstowe). Przykład 1.
Słownik algebraicznych elementów VT = {a, b, +, -, *, /, ( )},
S - symbol początkowy.
Prodykcji:


Wyprowadzenie łańcuchy (a+b*b) - a/b :



Drzewo wyprowadzenia.

Sld.10.10. Przykład 2
Gramatyka G = (V, T, P, S),
gdzie V={S}, T = {a, b) i P= {S� aSb, S� ab}.
Jedyną zmienną jest S; a i b są symbolami końcowymi.
Produkcje: S � aSb oraz S � ab.
Stosując pierwszą z nich n- 1 razy, a następnie jeden raz drugą, otrzymujemy
S ? aSb ? aaSbb ? a3Sb3 ? ? a n-1Sbn-1 ? anbn

S ?* anbn.

Sld.10.11. Przykład 3
Gramatyka G = (V, T, P, S),
gdzie V = {S, A, B}, T = {a, b} ,
Produkcje:
S�aB A�bAA
S�bA B�b
A�a B�bS
A�aS B�aBB
Językiem L(G) jest zbiór wszystkich słów z T+ złożonych z jednakowej liczby symboli a i b.
Sld. 10. 12. Przykład 4. Gramatyka typu trzy (regularna)
Gramatyka
G = (VT, VN, P, S), VT = {a, b, 0, 1}, VN = {S, L}.
Produkcje P:
S? aL, S? bL; S? a; S? b;
L? 0; L?1; L? a, L? b; L? 0L; L? 1L; L? aL; L? bL.
Sld. 13. Rownowazność gramatyk i automatów