• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Gramatyka bezkontekstowa

    Przeczytaj także...
    Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.Palindrom (gr. palindromeo – biec z powrotem) – wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.
    Język regularny (ang. regular language) to język formalny taki, że istnieje automat o skończonej liczbie stanów potrafiący zdecydować, czy dane słowo należy do języka. Równoważnie, taki, że istnieje dlań gramatyka regularna.

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

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




    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.018 sek.