Computability and Complexity

Table of Contents This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is Computer Science and Math students with some background in programming, data structures, and discrete math, such as a sophomore in a Computer Science program. Introduction100% Formal Languages75% Chomsky Hierarchy100% Regular Languages100% - sample DFA inputs Context Free Languages100% - sample PDA inputs Context Sensitive Languages100% - sample LBA inputs Unrestricted Languages100% - sample TM inputs Other Language Classes50% Counting Languages100% - sample CA inputs Computability25% Decidability100% Reducibility00% Complexity25% Time Complexity00% P00% P-Complete00% NP00% NP-Complete00% Space Complexity00% L00% NL00% NL-Complete00% PSPACE00% PSPACE-Complete00% References and Further Reading50% Computer science C 50%