Language EquationsBeginning with an informal introduction to language equations, this book presents a framework for a general theory for solving systems of equations and relations between languages. Classical language equations, generalized derivatives, Boolean language equations, and implicit equations are presented systematically. An exploration of mixed systems and open problems rounds out the presentation. |
Contents
Preface | 1 |
Classical Language Equations and the Substitution Property | 3 |
Overview of the Book | 7 |
Copyright | |
15 other sections not shown
Other editions - View all
Common terms and phrases
A-property with respect aa(a algorithm arbitrary languages assume automata boolean automaton boolean language equations Chapter complementation Consider the equation Consider the following consists of union constant languages construction context-free grammar context-free languages defined derivatives determine empty word EX{a EXA CONST EXA REG example exists a solution explicit language relations explicit relations expressions in EXA finite automaton following system given system implicit equations implicit language equations induction infinitely many solutions L₁ Leiss Lemma maximal solution mixed system nondeterministic finite automata nonempty nonreturning normal form obtain one-letter alphabet parametric representation PROOF Proposition regular expressions regular languages regular solution Section solution exists solve structural induction subrelations subset superrelation system of equations system of implicit two-sided language equations union and left-concatenation unique solution variables X1 verify X-property X₁ yields Z-test