Jeśli gramatyki są tej postaci, to w żaden sposób nie da się w jednym wyprowadzeniu użyć reguł obu gramatyk.
Algorytm taki nie istnieje dla dopełnienia języka (zbioru wszystkich słów które nie należą do danego języka). Jest nawet możliwe, że dany język opisuje jakaś gramatyka, ale dla zbioru słów nie należących do niego nie ma żadnej gramatyki.
Dla dwóch gramatyk potrafimy też znaleźć gramatykę przecięcia języków (zbioru słów należących do obu języków), ale jej postać może być o wiele trudniejsza od postaci gramatyk oryginalnych.
Klasy gramatyk Ograniczając postać reguł wyprowadzania, otrzymujemy klasy gramatyk, takie jak (szczegółowo w artykule hierarchia Chomskiego): gramatyki regularne gramatyki bezkontekstowe gramatyki bezkontekstowe w postaci normalnej Chomskiego gramatyki bezkontekstowe w postaci normalnej Greibach gramatyki kontekstowe gramatyki rekurencyjnie przeliczalne (bez ograniczeń na postać reguł)
Gramatyka regularna (odpowiednio: bezkontekstowa, kontekstowa) zawsze generuje język regularny (odp.: bezkontekstowy, kontekstowy). Jednak możliwe jest też, że pewna gramatyka, która nie jest regularna (bezkontekstowa, kontekstowa), generuje język regularny (bezkontekstowy, kontekstowy). W takim przypadku zawsze istnieje też gramatyka o regułach prostszej postaci generująca ten sam język.
Zobacz też parser
Linki zewnętrzne [dostęp 2026-01-16].
Kategoria:Języki formalne Kategoria:Gramatyka