Language Equations

We give a very informal overview of language equations; this is done by drawing on analogies between them and well-known, ordinary arithmetic equations, such as linear equations. The purpose of this chapter is to provide motivation for our study of language equations; more exact definitions are provided in the next chapter.

Formal definitions of the central concepts of our study are given, along with comments on their influence on, and relevance to, language equations. We first discuss alphabets, constant languages, operations, variables, and expressions; then, we give formal definitions of equations and relations and what constitutes a solution of a given system. The chapter concludes with numerous examples of systems of equations and relations which outline and delineate the research to be discussed in subsequent chapters.

We define classical language equations and relate them to nondeterministic finite automata. Then, we give two quite different solution approaches, both constructive. One is based on syntactic properties of the equations and essentially yields regular expressions as solutions. The other is by construction of nondeterministic finite automata. Advantages and disadvantages of both approaches are discussed; the second method (construction of a nondeterministic finite automaton) prepares us for the construction of a different kind of finite automaton (namely boolean) in the next chapter. The first method (construction of a regular expression) motivates a discussion of the substitution property, a property that holds for our solutions if OP does not contain the complementation or the intersection operator. We conclude this chapter by commenting on context-free grammars and the equations they engender.

We define boolean language equations and relate them to boolean automata. Boolean language equations are explicit equations over an arbitrary alphabet in which union, left-concatenation, and complementation may occur. Boolean automata are a generalization of nondeterministic finite automata that are able to accommodate, in a natural way, the complementation operation. We first show that not every boolean equation has a solution. Then, we give a constructive approach to solving any system of boolean equations that has a solution. We also give a complete characterization of the existence of solutions, decide whether more than one solution exists, give a representation of all solutions if more than one exists, and show that any boolean equation whose constant languages are regular must have a regular solution, if it has any.

In Section 4.4, we defined generalized derivatives. This chapter attempts to take derivatives as far as we can. In particular, we define them for the most general expressions considered in this book, namely expressions with union, concatenation, star, and complementation. We formulate the corresponding version of the λ-property and derive several useful properties of these derivatives. Most significantly, it allows us to show that any explicit equation has a unique solution, provided its expression has this λ-property. We conclude the chapter with a discussion of techniques that permit us to determine whether a given word is in the solution, even though that solution may not be regular.

Star equations are explicit language equations where the operators are union, left-concatenation, and star. If the constants are context-free, these equations always have a context-free solution. If the constants are regular, the solution is not guaranteed to be regular.

We restrict the underlying alphabet to one letter, denoted by a. Languages over {a} have interesting properties, some of which we derive. Then, we use them to show that any system of explicit equations over the alphabet {a} where the operators are union, unrestricted concatenation, and star have solutions that are expressible as regular expressions in terms of the constant languages only. Most importantly, we provide a complete solution of the problem, including a parametric representation of all solutions if there is more than one. We also study the case (in Section 7.7) where complementation is added to this catalog of operators and show that such equations need not have context-free solutions even if the constants are single letters.

We begin our coverage of implicit equations by considering the exact analogue to the classical (explicit) equations solved in Chapter 3. Specifically, the operations are union and left-concatenation and the constants are over an arbitrary alphabet. We first establish that, in contrast to explicit equations, implicit ones need not have any solutions. Furthermore, there exist implicit equations with context-free constants whose only solutions are non-context-free. Then we show a general criterion for the existence of a solution. This criterion is constructive if the constants are regular. Furthermore, the criterion gives rise to a test whether there exist finitely or infinitely many solutions. If the constants are regular, solutions can be constructed effectively; moreover, if there are finitely many solutions, all solutions can be constructed, and if there are infinitely many, an arbitrarily large number of them can be constructed.

While systems of language equations have been studied in various contexts, the corresponding problems for general relations between languages have not received much attention. In this chapter, we examine relations where the operations involved are unrestricted union and left-concatenation; in other words, precisely the operations involved in classical equations. Note that for classical equations, each variable is equated to exactly one expression. In this chapter, relations also include the case of several equations for the same variable. First, we look at single explicit relations and resolve the question of whether there exists a solution, study how to find all solutions, and investigate adequate representations for the solutions. Then, we focus on systems of several explicit relations; the questions here are significantly more complicated since for a single variable X, there may be three types of relations, namely equality (=), superrelation (⊒), and subrelation (⊑). We consider, first, decoupled systems, where for each variable, at most one of the three relation types may occur. We study methods to answer the questions of whether there exists a solution, whether there is more than one solution, and how to represent these solutions.

We describe how to solve systems of implicit language relations where the operations involved are union and concatenation from the left by a constant. This continues our study of language relations begun in the previous chapter. Implicit relations express a constant language in terms of an expression involving variables and require that the variables be determined so that the relation is satisfied. Primarily we consider systems of relations of the following three types: equality [L = α(X ₁,…,X _n )], superrelation [L ⊒ α(X ₁,…,X _n )], and subrelation [L ⊑ α(X ₁,…,X _n )]. Building on results derived for implicit equations (in Chapter 8), we derive a complete characterization of the existence of a solution of a given system. This is in contrast to explicit language relations where no complete characterization of solutions is known. We also address the question of uniqueness and the effectiveness of our constructions.

Two-sided language equations are the most general types of language equations. We discuss several approaches to determining whether a solution exists and of determining such a solution. The question of uniqueness is also of interest. However, in general, none of these approaches is guaranteed to work; in fact, it is not known how to determine whether a given system of m two-sided equations in n variables has a solution, even in the case where m = n = 1.

We address the question of combining explicit and im­plicit equations. It turns out that the existence of a parametric representation of all solutions of the explicit equations contained in the mixed system, together with a solution method for implicit systems, yields a general method for determin­ing whether such a system has a solution, and if so, how to find it. Consequently, provided there is at most one explicit equation for each variable, we can solve such systems in the case where the operations are union and left-concatenation, as well as in the case where the alphabet contains one letter, the constants are regular, and the operations are union, concatenation, and star.

We will give a list of problems that have not yet been resolved. This list complements the open problems (mainly directly related to material covered there) that have already been mentioned in the appropriate chapters. The difficulty of the problems ranges from fairly simple to (most likely) impossible to solve. The nature of a book such as this is that it provides a snapshot of what we know about the general theory, at a certain point in time. It should be clear that one might well find solutions to some of the (easier) problems listed here were one to work on them just another six months or a year.