Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 12

Trzecie wydanie zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Wybrałem ten temat z kilku powodów. Po pierwsze, wypełnia oczywistą lukę w poprzednim ujęciu teorii automatów i języków formalnych. Starsze wydania wprowadzały pojęcia automatów skończonych i maszyn Turinga w wariantach deterministycznych i niedeterministycznych, ale omawiałem w nich tylko niedeterministyczne wersje automatów ze stosem. Dodanie omówienia deterministycznych automatów ze stosem jest brakującym fragmentem układanki.

Po drugie, teoria deterministycznych języków bezkontekstowych jest podstawą gramatyk LR(k), ważnego i nietrywialnego zastosowania teorii automatów w projektowaniu języków programowania i kompilatorów. To zastosowanie łączy wiele kluczowych koncepcji, w tym równoważność deterministycznych i niedeterministycznych automatów skończonych oraz przekształcanie gramatyk bezkontekstowych na automaty ze stosem i odwrotnie, doprowadzając do wydajnej i pięknej metody parsingu. Mamy tu więc rzeczywiste współdziałanie teorii i praktyki.

Na koniec zagadnienie to wydaje się nie dość wyczerpująco omówione w istniejących podręcznikach teorii obliczeń, jeśli weźmiemy pod uwagę jego ważność jako naturalnego zastosowania teorii automatów. Gramatyki LR(k) studiowałem lata temu, ale nie osiągnąłem wówczas pełnego zrozumienia ich działania i nie dostrzegłem, jak pięknie pasują one do teorii deterministycznych języków bezkontekstowych. Pisząc ten podrozdział, miałem na celu przedstawienie intuicyjnego, ale ścisłego wprowadzenia do tej dziedziny, zarówno dla teoretyków, jak i praktyków, a tym samym chciałem przyczynić się do szerszego docenienia tych zagadnień. Muszę jednak dodać pewne ostrzeżenie: część materiału zawartego w tym podrozdziale jest dość wymagająca, zatem nauczyciel prowadzący pierwszy, podstawowy wykład teorii może wybrać go na lekturę dodatkową. Późniejsze rozdziały nie zależą i nie odwołują się do treści tego podrozdziału.

Wiele osób miało bezpośredni lub pośredni udział w powstawaniu tego wydania. Jestem wdzięczny recenzentom Christosowi Kapoutsisowi i Cem Say, którzy przeczytali szkic nowej części i podzielili się wartościowymi uwagami. W produkcji brało udział wiele osób z Cengage Learning, a szczególnie Alyssa Pratt i Jennifer Feltri-George. Suzanne Huizenga zredagowała tekst, a Laura Segel z firmy ByteGraphics przygotowała nowe ilustracje i zmodyfikowała niektóre spośród starszych rysunków.

Chciałbym podziękować moim asystentom z MIT, Victorowi Chenowi, Andy’emu Druckerowi, Michaelowi Forbesowi, Elenie Grigorescu, Brendanowi Juba, Christosowi Kapoutsisowi, Jonowi Kelnerowi, Swastikowi Kopparty, Kevinowi Matulef, Amandzie Redlich, Zackowi Remscrimowi, Benowi Rossmanowi, Shubhangi Saraf oraz Orenowi Weimannowi. Każde z nich pomogło mi, omawiając nowe zadania i ich rozwiązania, i dając wgląd w to, jak dobrze nasi studenci rozumieją zawartość wykładu. Praca z tak utalentowanymi i entuzjastycznymi młodymi ludźmi jest prawdziwą przyjemnością.

Wielką nagrodą jest otrzymywanie e-maili z uwagami i komentarzami z całego świata. Dziękuję za wszystkie sugestie, pytania i pomysły. Oto lista tych korespondentów, których uwagi wpłynęły na kształt tego wydania:

Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer,Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, Cheng-Chung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, Hans-Rudolf Metz, Mladen MikŜa, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Tas¸demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vazquez, Phanisekhar Botlaguduru Venkata, Benjamin Bing-Yi Wang, Lutz Warnke, David Warren, ThomasWatson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi.

Ponad wszystko zaś dziękuję mojej rodzinie – mojej żonie Inie i naszym dzieciom Racheli i Aaronowi. Czas jest skończony i umyka szybko. Wasza miłość jest wszystkim.

Michael Sipser

Cambridge, Massachusetts, kwiecień 2012