Theory of Computation

\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\N}{{\mathbb N}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\R}{{\mathbb R}} \newcommand{\Zpos}{{{\mathbb Z}^+}} \newcommand{\SUB}{\subseteq} \newcommand{\SUP}{\supseteq} \newcommand{\PSUB}{\varsubsetneq} \newcommand{\PSUP}{\varsupsetneq} \newcommand{\SETDIFF}{\smallsetminus} \newcommand{\st}{\,|\,} \newcommand{\ab}{\mbox{$\{a,b\}$}} \newcommand{\aetc}[2]{\mbox{{${#1}_1{#1}_2\ldots {#1}_{#2}$}}} \newcommand{\varep}{\varepsilon} \newcommand{\fsafig}[1]{\medskip\centerline{\eps{fsa#1}}\medskip} \newcommand{\REOR}{\hbox{$\,|\,$}} \newcommand{\POW}{{\mathscr P}} \newcommand{\EMPTYSTRING}{\varepsilon} \newcommand{\PRODUCES}{\longrightarrow} \newcommand{\YIELDS}{\Longrightarrow} \newcommand{\YIELDSTAR}{{\Longrightarrow}^*} \newcommand{\NT}[1]{\hbox{$\langle$\textit{#1}$\rangle$}} \newcommand{\BNFPRODUCES}{\hbox{\texttt{::=}}} \newcommand{\BNFALT}{\hbox{$|$}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Chapter 17 Theory of Computation

In this chapter we will study languages,formal language theory, grammars, Turing Machines, and computability. Our intent is to examine the question of how, and which, languages can be mechanically generated and recognized; and, ultimately, to see what this tells us about what computers can and can’t do.

Prev Top Next