Formal languages, automata, and complexity

212,917pages on
this wiki
Add New Page
Add New Page Discuss this page0

The plan of this work is similar to that of J. Glenn Brookshear's Theory of Computation: Formal Languages, Automata, and Complexity ISBN 0805301437 with some changes, although the actual text will vary greatly from his work.

It is my hope that this work will become an article submitted for publication in the Academic Publishing Wikia at in the Journal of Computer Science and Software Engineering. There is a need for a firm academic basis to support the aims of the Journal with respect to the dissemination of knowledge about the power of computers to implement algorithmic process and reach solutions.

  • Preliminaries
  • Review of Set Theory
  • Grammatical Basis of Language Theory
  • Historical Background
  • Preview of Subsequent Chapters
  • Finite Automata and Regular Languages
  • Lexical Analysis
  • Deterministic Finite Automata
  • Limits of Deterministic Finite Automata
  • Regular Grammars
  • Regular Expressions
  • Summary
  • Pushdown Automata and Context-Free Languages
  • Pushdown Automata
  • Context-Free Grammars
  • LL(k) and LR(k) Parsers
  • Turing Machines and Phrase-Structure Languages
  • Turing Machines
  • Modular Construction of Turing Machines
  • Turing Machines as Language Acceptors
  • Turing-Acceptable Languages
  • Beyond Phrase-Structure Languages
  • Computability
  • Recursive Function Theory
  • Primitive Recursive Functions
  • Partial Recursive Functions
  • The Power of Programming Languages
  • Summary
  • Complexity
  • Complexity of Computations
  • Complexity of Algorithms
  • Complexity of Problems
  • Time Complexity of Language Recognition
  • Nondeterministic Mechanical Time Complexity
  • Summary
  • Some Important Unsolvable Problems

Also on Fandom

Random wikia