• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Lemat o pompowaniu dla języków bezkontekstowych



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Lemat Ogdena to uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Służy do udowadniania, że dany język nie jest językiem bezkontekstowym.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.

    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.

    Spis treści

  • 1 Treść lematu
  • 2 Dowód lematu
  • 3 Technika dowodzenia
  • 4 Zobacz też
  • 5 Przypisy
  • 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 regularnych – twierdzenie służące do dowodzenia, że dany język nie jest językiem regularnym.


    Podstrony: 1 [2] [3] [4]



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

    Reklama