`- AUTOMATA THEORY,
`LANGUAGES,
`COMPUTATION
`
`AND
`
`JOHN E. HOPCROFT
`
`JEFFREY D. ULLMAN
`
` NLAAt UI
`
`aL\\\\
`
`
`a)‘
` a
`
`LiL iif
`LRTA
`
`
`
`
`WATEAM
`
`
`
`WU
`
`WN
`
`EXPERIAN EXHIBIT 1011
`IPR2023-01406
`
`EXPERIAN EXHIBIT 1011
`IPR2023-01406
`
`
`
`
`
`
`
`LANGUAGES,
`COMPUTATION
`
`AND
`
`JOHN E. HOPCROFT
`Cornell University
`
`JEFFREY D. ULLMAN
`Princeton University
`
`A
`vv
`
`SLEY PUBLISHING COMPANY
`ADDISON-WE
`Menlo Park, California
`Reading, Massachusetts *
`Ontario + Sydney
`London + Amsterdam ° Don Mills,
`
`
`
`
`
`
`
`
`Hoperoft, JohnE.,
`
`
`
`
`
`
`
`
`
` juages, and
`
`computation.
`
`
`
`Copyright © 1979 by
`Addison-Wesley Publishing Company, Inc.
`Philippines copyright 1979 by
`Addison-Wesley Publishing Company,Inc.
`All rights reserved. No part of this publication may
`be reproduced,stored in a retrieval system, or
`transmitted, in any form or by any means,
`sictronic, mechanical, photocdpying, recording, oF
`otherwise, without the prior written permission of
`the publisher. Printed in the United States of
`Amer1a. Published simultaneously in Canada.
`Library of Congress Catalog Card No. 78-67950.
`ISBN: 0-201-02988-x
`ST-DO-943210
`
`Library of CongressCatalogingin Publica fon
`
`
`
`
`Bibliography: Pp.
`
`Includes index. .
`oh
`
`
`1. Machine
`theory.
`
`
`3. Computational
`Jeffrey D., 1942-
`Qn267.456.°
` 629.81512
`
`
`ISBN 0-201-02988-x
`
`
`
`
`
`CHAPTER
`
`
`
`PRELIMINARIES
`
`In this chapter we survey the principal mathematical ideas necessary for under-
`standing the material in this book. These concepts include graphs,trees, sets,
`relations, strings, abstract languages, and mathematical induction. Wealso pro-
`vide a brief introduction to, and motivationfor, the entire work. The reader with a
`background in the mathematical subjects mentioned can skip to Section 1.6 for
`motivational remarks.
`
`1.1 STRINGS, ALPHABETS, AND LANGUAGES
`
`A “symbol”is an abstract entity that we shall not define formally, just as “point”
`and “line” are not defined in geometry. Letters and digits are examples of
`frequently used symbols. A string (or word) is oliReavence of symbols jux-
`taposed. For example, a, b, and c are symbols and abc isa string. The length ofa
`string w, denoted |w/|, is the number of symbols composingthestring. For exam-
`ple, abcb has length 4. The emptystring, denoted by ¢,is the string consisting of
`zero symbols. Thus |¢| = 0.
`:
`:
`A prefix of a string is any numberofleading symbols of that string, and a
`suffix is any numberoftrailing symbols. For example,string abc has prefixes€,
`a, ab,
`and abe:its suffixes are ¢, c, bc, and abc. A prefix or suffix of a string, other than the
`_
`String
`itself, is called a proper
`prefix or suffix.
`8
`oO
`The concate tion‘of cae is the string formed by writing the first,
`
`lo
`d, with no intervening space. For example, the concatena-
`
`ise
`is doghouse. Juxtaposition is used as the concatenation
`
`and x arestrings, then wx is the concatenation of these two
`
`
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
