• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Lemat Ogdena

    Przeczytaj także...
    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.
    Lemat o pompowaniu dla języków bezkontekstowych to twierdzenie służące do udowadniania, że dany język nie jest bezkontekstowy. Jego uogólnieniem jest lemat Ogdena.

    Lemat Ogdena – uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Służy do udowadniania, że dany język nie jest językiem bezkontekstowym.

    Lemat mówi że:
    Dla każdego języka bezkontekstowego istnieje taka stała że dla każdego słowa zawierającego co najmniej wyróżnionych pozycji, możemy podzielić na w taki sposób, że:

  • słowo zawiera (przynajmniej jedną) wyróżnioną pozycję,
  • słowo zawiera co najwyżej wyróżnionych pozycji,
  • dla każdego mamy




  • Reklama

    Czas generowania strony: 0.725 sek.