Hardware Reference
In-Depth Information
2.2.3
Language Equations Under Bounded Parallel Composition
Theorem 2.19.
The largest solution of the equation
A
˘
l
X
C
is the language
S
D
.A
*
O
\
C
*
.U;l/
/
+
U
[
O
:
Proof.
A
˘
l
f
˛
g
C
,
[
O/
?
.A
*
O
\f
˛
g
*
I
\
.I
*
.U;l/
/
+
I
[
O
\
C
D;,
A
*
O
\f
˛
g
*
I
\
C
*
.U;l/
D;,
˛
62
.A
*
O
\
C
*
.U;l/
/
+
U
[
O
,
˛
2
.A
*
O
\
C
*
.U;l/
/
+
U
[
O
t
2.3
Solution of Equations Over Regular Languages
and Finite Automata
Language equations can be solved effectively when they are defined over languages
that can be computed with finite procedures. Usually such languages are presented
through their corresponding mathematical machines, e.g., finite automata for regular
languages. In the following sections, equations over various classes of automata are
studied, like FAs and FSMs, specializing the theory of equations to their associated
languages. A key issue to investigate is the closure of the solution set with respect
to a certain type of language, e.g., when dealing with FSM language equations we
require that the solutions are FSM languages. This cannot be taken for granted,
because the general solution of abstract language equations is expressed through the
operators of complementation and composition, which do not necessarily preserve
certain classes of languages.
2.3.1
An Algorithm to Solve Equations Over Regular Languages
and Automata
Two well-known results [63] are that non-deterministic finite automata are equiv-
alent (with respect to language equality) to deterministic ones and that regular
expressions are equivalent to finite automata. By applying the algorithm of subset
construction one converts a NDFA into an equivalent DFA (it is complete by con-
struction). Given an NDFA F
Dh
S; ˙; ; r; Q
i
, the process of subset construction
Search WWH ::
Custom Search