Formal Language - A Practical Introduction
Author: Adam Brooks Webber
Publisher: Franklin, Beedle & Associates, Inc.
January 23, 2008
Pages: 388
Language: English
Official Author Website (Lecture Slides) http://www.webber-labs.com/fl/
TABLE OF CONTENTS
* Introduction and Chapter 1: Fundamentals
* Chapter 2: Finite Automata
* Chapter 3: Closure Properties for Regular Languages
* Chapter 4: DFA Applications
* Chapter 5: Nondeterministic Finite Automata
* Chapter 6: NFA Applications
* Chapter 7: Regular Expressions
* Chapter 8: Regular Expression Applications
* Chapter 9: Advanced Topics in Regular Languages
* Chapter 10: Grammars
* Chapter 11: Non-Regular Languages
* Chapter 12: Context-Free Languages
* Chapter 13: Stack Machines
* Chapter 14: The Context-Free Frontier
* Chapter 15: Stack Machine Applications
* Chapter 16: Turing Machines
* Chapter 17: Computability
* Chapter 18: Uncomputability
* Chapter 19: Cost Models
Covers wide range of topics in Theoretical Computer Science with some programming applications.
Used by University of Vermont, CS125 (Computer Science 125 - Computability and Complexity)
Alan Ling, Pippin Wolfe, Chris Skalka
<p>formal language
A P R A C T I C A L
I N T R O D U C T I O N
Adam Brooks Webber
Monmouth College
Franklin, Beedle & Associates, Inc.
8536 SW St. Helens Drive, Ste. D
Wilsonville, Oregon 97070
503/682-7668
www.fbeedle.com
Publisher
Jim Leisy (jimleisy@fbeedle.com)
Production Editor
Tom Sumner
Editor
Stephanie Welch
Order Processing
Jaron Ayres
Printed in the U.S.A.
© 2008 Franklin, Beedle & Associates, Incorporated. No part of this book may be
reproduced, stored in a retrieval system, transmitted, or transcribed, in any form or by
any means—electronic, mechanical, telepathic, photocopying, recording, or otherwise—
without prior written permission of the publisher. Requests for permission should be
addressed as follows:
Rights and Permissions
Franklin, Beedle & Associates, Incorporated
8536 SW St. Helens Drive, Ste. D
Wilsonville, Oregon 97070
Library of Congress Cataloging-in Publication Data
Webber, Adam Brooks.
Formal language : a practical introduction / Adam Brooks Webber.
p. cm.
ISBN-13: 978-1-59028-197-0
1. Formal languages--Textbooks. 2. Computational complexity--Textbooks. I. Title.
QA267.3.W423 2007
005.13'1--dc22
2007027145
iii
c o n t e n t s
Preface
viii
CHAPTER 1 Fundamentals
11
1.1
Alphabets
12
1.2
Strings
12
1.3
Languages
14
Exercises
15
CHAPTER 2 Finite Automata
7
2.1
Man, Wolf, Goat, and Cabbage
8
2.2
Not Getting Stuck
10
2.3
Deterministic Finite Automata
10
2.4
The 5-Tuple
13
2.5
The Language Accepted by a DFA
14
Exercises
15
CHAPTER 3 Closure Properties for Regular Languages
21
3.1
Closed Under Complement
22
3.2
Closed Under Intersection
23
3.3
Closed Under Union
26
3.4
DFA Proofs Using Induction
27
3.5
A Mystery DFA
30
Exercises
32
CHAPTER 4 Deterministic-Finite-Automata Applications
35
4.1
An Overview of DFA Applications
36
4.2
A DFA-based Text Filter in Java
36
4.3
Table-driven Alternatives
41
Exercises
43
CHAPTER