Information Technology Reference
In-Depth Information
{{
2
}
2
·
a
}
{{
2
}
1
·
a
}
{{
2
}
1
·
a
}
S
0
S
1
S
2
{{
2
}
1
·
a
}
{{
2
}
0
·
a
}
Fig. 6.
Unambiguous constraint automaton for the flip-flop defined in Figure 4
{{
2
}
0
·
a
}
a
3
b
a
5
b
a
7
b
Fig. 7.
Automaton for (
a
3
b
|
a
5
b
|
a
7
b
)
2
a
3
b
a
5
b
a
7
b
S
0
S
1
S
2
(
a
3
b
a
5
b
a
7
b
)
2
|
|
Regex-to-CE, Bounded Repetition,
Catenation (7, 10, 9)
Σ
−
{∅
3
·
a
,∅
1
·
b
}∨{∅
5
·
a
,∅
1
·
b
}∨{∅
7
·
a
,∅
1
·
b
}
)
2
(
0
0
2
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
∨
0
2
0
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
∨
2
0
0
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
∨
1
1
0
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
∨
1
0
1
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
∨
0
1
1
{∅
3
·
a
,∅
1
·
b
}
· {∅
5
·
a
,∅
1
·
b
}
· {∅
7
·
a
,∅
1
·
b
}
Bounded Repetition (10)
{∅
14
·
a
,∅
2
·
b
}∨{∅
10
·
a
,∅
2
·
b
}∨{∅
6
·
a
,∅
2
·
b
}∨
{∅
3
·
a
,∅
1
·
b
}·{∅
5
·
a
,∅
1
·
b
}
∨
{∅
3
·
a
,∅
1
·
b
}·{∅
7
·
a
,∅
1
·
b
}
∨
Bounded Repetition,
Power
0
elimination (10)
{∅
5
·
a
,∅
1
·
b
}·{∅
7
·
a
,∅
1
·
b
}
{∅
14
·
a
,∅
2
·
b
}∨{∅
10
·
a
,∅
2
·
b
}∨{∅
6
·
a
,∅
2
·
b
}∨
{∅
8
·
a
,∅
2
·
b
}∨{∅
10
·
a
,∅
2
·
b
}∨{∅
12
·
a
,∅
2
·
b
}
Catenation (9)
= {∅
14
·
a
,∅
2
·
b
}∨{∅
10
·
a
,∅
2
·
b
}∨{∅
6
·
a
,∅
2
·
b
}∨
{∅
8
·
a
,∅
2
·
b
}∨{∅
12
·
a
,∅
2
·
b
}
Removal of duplicates
Example 8.
The following example shows the derivation of a constraint from state
S
0
to
S
2
in Figure 8a, involving a loop sandwiched between two compulsory single-element
transitions, thus demonstrating the use of modulo sets.
a
(
a
5
b
3
)
∗
a
− {∅
1
·
a
,∅
0
·
b
}·{∅
5
·
a
,∅
3
·
b
}
∗
· {∅
1
·
a
,∅
0
·
b
}
Σ
Regex-to-CE (7)
{∅
1
·
a
,∅
0
·
b
}·{{
5
}
0
·
a
,{
3
}
0
·
b
}·{∅
1
·
a
,∅
0
·
b
}
Unbounded Repetition (11)
{{
5
}
2
·
a
,{
3
}
0
·
b
}
Catenation (9)
