book

An Introduction to Formal Languages and Automata, 7th Edition

by Peter Linz, Susan H. Rodger

February 2022

Beginner to intermediate

572 pages

13h

English

Jones & Bartlett Learning

Read now

Unlock full access

SetsFunctions and RelationsGraphs and TreesProof Techniques
LanguagesGrammarsAutomata

Deterministic Accepters and Transition GraphsLanguages and Dfa’sRegular Languages
Definition of a Nondeterministic AccepterWhy Nondeterminism?
Formal Definition of a Regular ExpressionLanguages Associated with Regular Expressions
Regular Expressions Denote Regular LanguagesRegular Expressions for Regular LanguagesRegular Expressions for Describing Simple Patterns
Right- and Left-Linear GrammarsRight-Linear Grammars Generate Regular LanguagesRight-Linear Grammars for Regular LanguagesEquivalence of Regular Languages and Regular Grammars
Closure under Simple Set OperationsClosure under Other Operations
Using the Pigeonhole PrincipleA Pumping Lemma
Examples of Context-Free LanguagesLeftmost and Rightmost DerivationsDerivation TreesRelation Between Sentential Forms and Derivation Trees
Parsing and MembershipAmbiguity in Grammars and Languages
A Useful Substitution RuleRemoving Useless ProductionsRemoving λ-ProductionsRemoving Unit-Productions
Chomsky Normal FormGreibach Normal Form
Definition of a Pushdown AutomatonThe Language Accepted by a Pushdown Automaton
Pushdown Automata for Context-Free LanguagesContext-Free Grammars for Pushdown Automata
A Pumping Lemma for Context-Free LanguagesA Pumping Lemma for Linear Languages
Closure of Context-Free LanguagesSome Decidable Properties of Context-Free Languages
Definition of a Turing MachineTuring Machines as Language AcceptersTuring Machines as Transducers
Equivalence of Classes of AutomataTuring Machines with a Stay-OptionTuring Machines with Semi-Infinite TapeThe Off-Line Turing Machine
Multitape Turing MachinesMultidimensional Turing Machines
Languages That Are Not Recursively EnumerableA Language That Is Not Recursively EnumerableA Language That Is Not Recursively Enumerable but Not Recursive
Context-Sensitive Languages and Linear Bounded AutomataRelation Between Recursive and Context-Sensitive Languages
Computability and DecidabilityThe Turing Machine Halting ProblemReducing One Undecidable Problem to Another
Primitive Recursive FunctionsAckermann’s Functionμ Recursive Functions
Matrix GrammarsMarkov AlgorithmsL-Systems
Pushdown Automata for LLParsingAlgorithm to Convert Context-Free Grammar to NPDA for LLParsing
LL(1) Parse Table
LL(1) Parsing Algorithm
Algorithm to Convert Context-Free Grammar to NPDA for LR Parsing
Algorithm to Build DFA Modeling LR Parsing
LR(1) Parsing ActionsLR(1) Parse Table Algorithm
LR(1) Parsing Algorithm

Content preview from An Introduction to Formal Languages and Automata, 7th Edition

Chapter 8 with the heading Properties of Context-Free Languages.

CHAPTER 8PROPERTIES OF CONTEXT-FREE LANGUAGES

The family of context-free languages occupies ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

An Introduction to Formal Languages and Automata, 6th Edition

Peter Linz

Formal Languages and Automata Theory

K.V.N. Sunitha

Advanced Engineering Mathematics, 7th Edition

Dennis G. Zill

Introduction to Probability

Joseph K. Blitzstein, Jessica Hwang

Publisher Resources

ISBN: 9781284231618