Introduction to Formal Language and Automata

ISBN-10: 0763737984

ISBN-13: 9780763737986

Edition: 4th 2006 (Revised)

Authors: Peter Linz

List price: $195.95
30 day, 100% satisfaction guarantee

If an item you ordered from TextbookRush does not meet your expectations due to an error on our part, simply fill out a return request and then return it by mail within 30 days of ordering it for a full refund of item cost.

Learn more about our returns policy


Fully revised, the new Fourth Edition of An Introduction to Formal Languages and Automata provides an accessible, student-friendly presentation of all material essential to an introductory Theory of Computation course. The text was designed to familiarize students with the foundations and principles of computer science and to strengthen the students' ability to carry out formal and rigorous mathematical arguments. In the new Fourth Edition, author Peter Linz has offered a straightforward, uncomplicated treatment of formal languages and automata and avoids excessive mathematical detail so that students may focus on and understand the underlying principles. In an effort to further the accessibility and comprehension of the text, he has added new illustrative examples throughout.
what's this?
Rush Rewards U
Members Receive:
You have reached 400 XP and carrot coins. That is the daily max!
Study Briefs

Limited time offer: Get the first one free! (?)

All the information you need in one place! Each Study Brief is a summary of one specific subject; facts, figures, and explanations to help you learn faster.

Add to cart
Study Briefs
SQL Online content $4.95 $1.99
Add to cart
Study Briefs
MS Excel® 2010 Online content $4.95 $1.99
Add to cart
Study Briefs
MS Word® 2010 Online content $4.95 $1.99
Add to cart
Study Briefs
MS PowerPoint® 2010 Online content $4.95 $1.99
Customers also bought

Book details

List price: $195.95
Edition: 4th
Copyright year: 2006
Publisher: Jones & Bartlett Learning, LLC
Publication date: 2/17/2006
Binding: Hardcover
Pages: 415
Size: 7.25" wide x 9.00" long x 1.00" tall
Weight: 1.892
Language: English

Introduction to the Theory of Computation
Mathematical Preliminaries and Notation
Functions and Relations
Graphs and Trees
Proof Techniques
Three Basic Concepts
Some Applications
Finite Automata
Deterministic Finite Accepters
Deterministic Accepters and Transition Graphs
Languages and Dfa's
Regular Languages
Nondeterministic Finite Accepters
Definition of a Nondeterministic Accepter
Why Nondeterminism?
Equivalence of Deterministic and Nondeterministic Finite Accepters
Reduction of the Number of States in Finite Automata
Regular Languages and Regular Grammars
Regular Expressions
Formal Definition of a Regular Expression
Languages Associated with Regular Expressions
Connection Between Regular Expressions and Regular Languages
Regular Expressions Denote Regular Languages
Regular Expressions for Regular Languages
Regular Expressions for Describing Simple Patterns
Regular Grammars
Right- and Left-Linear Grammars
Right-Linear Grammars Generate Regular Languages
Right-Linear Grammars for Regular Languages
Equivalence of Regular Languages and Regular Grammars
Properties of Regular Languages
Closure Properties of Regular Languages
Closure under Simple Set Operations
Closure under Other Operations
Elementary Questions about Regular Languages
Identifying Nonregular Languages
Using the Pigeonhole Principle
A Pumping Lemma
Context-Free Languages
Context-Free Grammars
Examples of Context-Free Languages
Leftmost and Rightmost Derivations
Derivation Trees
Relation between Sentential Forms and Derivation Trees
Parsing and Ambiguity
Parsing and Membership
Ambiguity in Grammars and Languages
Context-Free Grammars and Programming Languages
Simplification of Context-Free Grammars and Normal Forms
Methods for Transforming Grammars
A Useful Substitution Rule
Removing Useless Productions
Removing [lambda]-Productions
Removing Unit-Productions
Two Important Normal Forms
Chomsky Normal Form
Greibach Normal Form
A Membership Algorithm for Context-Free Grammars
Pushdown Automata
Nondeterministic Pushdown Automata
Definition of a Pushdown Automaton
The Language Accepted by a Pushdown Automaton
Pushdown Automata and Context-Free Languages
Pushdown Automata for Context-Free Languages
Context-Free Grammars for Pushdown Automata
Deterministic Pushdown Automata and Deterministic Context-Free Languages
Grammars for Deterministic Context-Free Languages
Properties of Context-Free Languages
Two Pumping Lemmas
A Pumping Lemma for Context-Free Languages
A Pumping Lemma for Linear Languages
Closure Properties and Decision Algorithms for Context-Free Languages
Closure of Context-Free Languages
Some Decidable Properties of Context-Free Languages
Turing Machines
The Standard Turing Machine
Definition of a Turing Machine
Turing Machines as Language Accepters
Turing Machines as Transducers
Combining Turing Machines for Complicated Tasks
Turing's Thesis
Other Models of Turing Machines
Minor Variations on the Turing Machine Theme
Equivalence of Classes of Automata
Turing Machines with a Stay-Option
Turing Machines with Semi-Infinite Tape
The Off-Line Turing Machine
Turing Machines with More Complex Storage
Multitape Turing Machines
Multidimensional Turing Machines
Nondeterministic Turing Machines
A Universal Turing Machine
Linear Bounded Automata
A Hierarchy of Formal Languages and Automata
Recursive and Recursively Enumerable Languages
Languages That Are Not Recursively Enumerable
A Language That Is Not Recursively Enumerable
A Language That Is Recursively Enumerable but Not Recursive
Unrestricted Grammars
Context-Sensitive Grammars and Languages
Context-Sensitive Languages and Linear Bounded Automata
Relation Between Recursive and Context-Sensitive Languages
The Chomsky Hierarchy
Limits of Algorithmic Computation
Some Problems That Cannot Be Solved by Turing Machines
Computability and Decidability
The Turing Machine Halting Problem
Reducing One Undecidable Problem to Another
Undecidable Problems for Recursively Enumerable Languages
The Post Correspondence Problem
Undecidable Problems for Context-Free Languages
A Question of Efficiency
Other Models of Computation
Recursive Functions
Primitive Recursive Functions
Ackermann's Function
[micro] Recursive Functions
Post Systems
Rewriting Systems
Matrix Grammars
Markov Algorithms
An Overview of Computational Complexity
Efficiency of Computation
Turing Machine Models and Complexity
Language Families and Complexity Classes
The Complexity Classes P and NP
Some NP Problems
Polynomial-Time Reduction
NP-Completeness and an Open Question
Free shipping on orders over $35*

*A minimum purchase of $35 is required. Shipping is provided via FedEx SmartPost® and FedEx Express Saver®. Average delivery time is 1 – 5 business days, but is not guaranteed in that timeframe. Also allow 1 - 2 days for processing. Free shipping is eligible only in the continental United States and excludes Hawaii, Alaska and Puerto Rico. FedEx service marks used by permission."Marketplace" orders are not eligible for free or discounted shipping.

Learn more about the TextbookRush Marketplace.