gramatyka formalna

gramatyka formalna,

inform. reguły określające pewien język formalny, tzn. zbiór słów (lub zdań) oraz ich strukturę.

Definiuje się ją jako układ 〈T, N, S, P〉, gdzie T, N są skończonymi zbiorami symboli, zw. odpowiednio terminalnymi i  nieterminalnymi, S — wyróżnionym symbolem nieterminalnym, zw. początkowym, P — skończonym zbiorem reguł gramatyki, czyli par słów x, y (ciągów symboli z sumy zbiorów T i N), oznaczanych x → y. Słowo v wywodzi się bezpośrednio ze słowa u, gdy w P jest reguła x → y taka, że x jest fragmentem u, a zastępując x przez y w słowie u, otrzymuje się v. Słowo v wywodzi się ze słowa u, gdy u = v lub gdy istnieje ciąg kolejno wywodzących się bezpośrednio słów u₀, ... , u_n taki, że u₀ = u, u_n = v. Językiem generowanym przez tę gramatykę jest zbiór wszystkich słów wywodzących się z symbolu S i zbud. z symboli terminalnych. Dla dowolnych słów u, v, x, symboli nieterminalnych A, B, symbolu terminalnego a gramatykę formalną (i generowany język) nazywa się typu 0, gdy nie ma ograniczeń na postać reguł, typu 1 (gramatyka kontekstowa) — gdy reguły są postaci uAv → uxv, typu 2 (gramatyka bezkontekstowa) — gdy reguły są postaci A → x, typu 3 (gramatyka regularna) — gdy reguły są postaci A → aB, A → Ba lub A → a. Okazuje się (N. Chomsky, 1962), że klasy języków typu 0, 1, 2, 3, są identyczne z klasami języków akceptowanych przez odpowiednie automaty abstrakcyjne: dowolne (maszyny Turinga), liniowo ograniczone, ze stosem, skończone.