Gramatyka bezkontekstowa
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.
🔥 Top keywords: Wikipedia:Strona głównaMistrzostwa Europy w Piłce Nożnej 2024Specjalna:SzukajWikipedia:O WikipediiMichał ProbierzMistrzostwa Europy w Piłce Nożnej 2020Kylian MbappéMistrzostwa Europy w piłce nożnejMistrzostwa Świata w Piłce Nożnej 2022Antoine GriezmannNicola ZalewskiMistrzostwa świata w piłce nożnej mężczyznReprezentacja Francji w piłce nożnej mężczyznDzień OjcaTaras RomanczukRomelu LukakuMistrzostwa Europy w Piłce Nożnej 2016Reprezentacja Polski w piłce nożnej mężczyznAdam BuksaZofia Noceti-KlepackaPolskaDidier DeschampsRobert LewandowskiMistrzostwa Świata w Piłce Nożnej 2026FentanylMistrzostwa Europy w Piłce Nożnej 2028N’Golo KantéOndrej DudaPałac Stolbergów we WrocławiuSłowacjaGheorghe HagiMistrzostwa Europy w Piłce Nożnej 2020/FinałCristiano RonaldoReprezentacja Rumunii w piłce nożnej mężczyznMistrzostwa Europy w Piłce Nożnej 2012Tadeusz GapińskiMistrzostwa Europy w Piłce Nożnej 2024 (eliminacje)Olivier GiroudDawid Podsiadło