本書是理論計(jì)算機(jī)科學(xué)方面的經(jīng)典教材，主要討論形式語(yǔ)言與自動(dòng)機(jī)理論、可計(jì)算性理論和計(jì)算復(fù)雜性理論等內(nèi)容。本書強(qiáng)調(diào)定義和定理的準(zhǔn)確性和嚴(yán)謹(jǐn)性，但在形式化證明中又非常注重符合直覺(jué)的理解，避免多余的數(shù)學(xué)細(xì)節(jié)。本書分為理論和應(yīng)用兩個(gè)部分：理論部分主要介紹有窮自動(dòng)機(jī)、正則語(yǔ)言和文法、上下文無(wú)關(guān)語(yǔ)言和文法、下推自動(dòng)機(jī)、圖靈機(jī)、形式語(yǔ)言和自動(dòng)機(jī)的層次結(jié)構(gòu)以及計(jì)算復(fù)雜性等內(nèi)容，應(yīng)用部分主要介紹編譯器和解析、LL解析以及LR解析。