gramatyka formalna
 
Encyklopedia PWN
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 terminalnyminieterminalnymi, 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 TN), 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 u0, ... , un taki, że u0 = u, un = 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 Ax, typu 3 (gramatyka regularna) — gdy reguły są postaci AaB, ABa lub Aa. 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.
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia