Gramatyka bezkontekstowa
| Ten artykuł od 2013-09 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 bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:
gdzie:
- – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje;
- – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.
Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.
Formalna definicja
Gramatyką bezkontekstową nazywa się czwórkę uporządkowaną gdzie:
- jest skończonym zbiorem symboli terminalnych,
- jest skończonym zbiorem symboli nieterminalnych,
- jest skończonym zbiorem reguł typu gdzie oraz
- jest wyróżnionym elementem początkowym.
Przykłady
- Przykład 1
- Gramatyka generuje język Ten język nie jest regularny.
- Przykład 2
- Język który jest językiem wszystkich palindromów nad alfabetem może być wygenerowany przez następującą gramatykę:
Postaci normalne
Każdy język bezkontekstowy nie zawierający słowa pustego może być wyrażony za pomocą gramatyki w postaci normalnej Greibach oraz postaci normalnej Chomskiego.
- p
- d
- e
Teoria automatów: języki formalne i gramatyki formalne
Hierarchia Chomsky’ego |
|
---|---|
Gramatyka formalna |
|
Język formalny |
|
Minimalny automat akceptujący |