Gramatyka kombinatoryczna

Wikipedia:Weryfikowalność
Ten artykuł od 2022-05 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Gramatyka kombinatoryczna – gramatyka formalna bez ograniczeń na postać reguł. W hierarchii Chomskiego jest to gramatyka typu 0. Generuje język rekurencyjnie przeliczalny.

Inne nazwy tego rodzaju gramatyki to: gramatyka rekurencyjnie przeliczalna, gramatyka struktur fazowych, gramatyka bez ograniczeń.

Teoria automatów: języki formalne i gramatyki formalne
Hierarchia Chomskiego
  • Typ 0
  • Typ 1
  • Typ 2
  • Typ 3
Gramatyka formalna
Język formalny
Minimalny automat akceptujący