Wcześniej użyliśmy formy Backusa–Naura (BNF) do napisania gramatyki dla języka logiki pierwszego rzędu. Gramatyka to zbiór reguł, które definiują strukturę drzewa dozwolonych fraz, a język to zbiór zdań zgodnych z tymi regułami. Języki naturalne nie działają dokładnie tak, jak język formalny logiki pierwszego rzędu — nie mają sztywnej granicy między zdaniami dopuszczalnymi i niedozwolonymi, ani nie mają pojedynczej, definitywnej struktury drzewiastej dla każdego zdania. Jednak w języku naturalnym ważna jest struktura hierarchiczna. Słowo „Zapasy” w „Zapasy zgromadzone w poniedziałek” nie jest tylko słowem ani rzeczownikiem; w tym zdaniu zawiera również frazę rzeczownikową, która jest przedmiotem następującej frazy czasownikowej. Kategorie składniowe, takie jak fraza rzeczownikowa lub fraza czasownikowa, pomagają ograniczyć prawdopodobne słowa w każdym punkcie zdania, a struktura frazy zapewnia ramy znaczenia lub semantyki zdania. Istnieje wiele konkurencyjnych modeli językowych opartych na idei hierarchicznej struktury składniowej; w tej części opiszemy popularny model zwany probabilistyczną gramatyka bezkontekstową lub PCFG. Gramatyka probabilistyczna przypisuje każdemu ciągowi prawdopodobieństwo, a „bezkontekstowa” oznacza, że dowolna reguła może być użyta w dowolnym kontekście: reguły dla frazy rzeczownikowej na początku zdania są takie same, jak dla innej frazy rzeczownikowej w dalszej części zdania. zdanie, a jeśli ta sama fraza występuje w dwóch miejscach, to za każdym razem musi mieć to samo prawdopodobieństwo. Zdefiniujemy gramatykę PCFG dla małego fragmentu języka angielskiego, który jest odpowiedni do komunikacji między agentami eksplorującymi świat wumpusa. Nazywamy ten język E0 . Reguła gramatyczna, taka jak
oznacza, że kategoria składniowa Adjs może składać się z pojedynczego Adjective z prawdopodobieństwem 0,80 lub z Adjective, po którym następuje ciąg tworzący Adjs, z prawdopodobieństwem 0,20.
Niestety gramatyka nadmiernie się generuje: to znaczy generuje zdania, które nie są gramatyczne, takie jak „Me go I”. Nie generuje też zbyt wiele: jest wiele zdań w języku angielskim, które odrzuca, na przykład „Myślę, że wumpus jest śmierdzący”. Zobaczymy, jak nauczyć się lepszej gramatyki później; na razie skupiamy się na tym, co możemy zrobić z tą bardzo prostą gramatyką.