Gramatyka bezkontekstowa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Gramatyka bezkontekstowagramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci:

Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.Język bezkontekstowy (ang. context-free language) to język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa.

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ą.

Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) są postaci:

Formalna definicja[ | edytuj kod]

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[ | edytuj kod]

    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[ | edytuj kod]

    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.





    Reklama