![](https://csdnimg.cn/release/download_crawler_static/10316002/bg10.jpg)
Complexity in Convex Languages 5
4 Complexity of Decision Problems
The results of this section are from [8]. Regular languages over an alphabet Σ are
languages that can be obtained from the basic languages ∅, {ε},and{a}, a ∈ Σ,
using a finite number of operations of union, product and star. Such languages
are usually denoted by regular expressions. If E is a regular expression, then
L(E) is the language denoted by that expression. For example, E =(ε ∪ a)
∗
b
denotes L =({ε}∪{a})
∗
{b}. We use the regular expression notation for both
expressions and languages. In contrast to other authors, we prefer to use the
same operator symbol in expressions as in languages. Thus ∪ denotes union,
juxtaposition denotes product, and
∗
denotes the star.
A deterministic finite automaton (DFA) is a quintuple D =(Q, Σ, δ, q
0
,F),
where Q is a finite, non-empty set of states, Σ is a finite, non-empty alphabet,
δ : Q × Σ → Q is the transition function, q
0
∈ Q is the initial state,andF ⊆ Q
is the set of final states.
As usual, a nondeterministic finite automaton (NFA) is a quintuple N =
(Q, Σ, η, S, F ), where Q, Σ,andF are as in a DFA, η : Q × Σ → 2
Q
is the
transition function,andS ⊆ Q is the set of initial states.Ifη also allows ε as
input, then we call N an ε-NFA.
The following questions were studied in [8]: If a regular language L is specified
by a DFA, how difficult is it to decide whether L isprefix-,suffix-,factor-,or
subword-convex, or -free, or -closed?
The most difficult case is that of factor-convexity. To solve this problem we
test whether L is not factor-convex, in which case there exist u, v, w ∈ Σ
∗
,such
that u v w,withu, w ∈ L and v ∈ L. Then there exist u
,u
,v
,v
such
that v = u
uu
and w = v
vv
= v
u
uu
v
.
Suppose D =(Q, Σ, δ, q
0
,F) is a DFA accepting L. We define an ε-NFA
N =(Q
,Σ,δ
, {q
0
},F
), where Q
= Q×Q×Q×{1, 2, 3, 4, 5}, q
0
=[q
0
,q
0
,q
0
, 1],
F
= F × (Q \ F ) × F ×{5},andδ
is defined below. States of N are quadruples,
where components 1, 2, and 3 keep track of the state of N as it is processing w,
v,andu, (respectively). The last component represents the mode of operation
of N.
The ε-NFA starts with the first three components in the initial state q
0
,and
the fourth in mode 1. Recall that the input string we are examining has the form
w = v
u
uu
v
. The automaton N operates in mode 1 for a while, reading the in-
put only in component 1 using δ
([p, q
0
,q
0
, 1],a)={[δ(p, a),q
0
,q
0
, 1]}, for all p ∈
Q, a ∈ Σ. Then it guesses nondeterministically that it has finished reading v
,
and switches to mode 2 using δ
([p, q
0
,q
0
, 1],ε)={[p, q
0
,q
0
, 2]}, for all p ∈
Q. In mode 2, component 1 continues to read the input u
uu
v
from the
state reached by v
, while component 2 reads that input from state q
0
us-
ing δ
([p, q, q
0
, 2],a)={[δ(p, a),δ(q, a),q
0
, 2]}, for all p, q ∈ Q, a ∈ Σ.Atsome
point N guesses that u
has been read and switches to mode 3 using the rule
δ
([p, q, q
0
, 2],ε)={ [p, q, q
0
, 3]}, for all p, q ∈ Q. Now all three components read
the input uu
v
, the first starting from the state reached by v
u
, the second
from the state reached by u
and the third from q
0
,usingδ
([p, q, r, 3],a)=
{[δ(p, a),δ(q, a),δ(r, a), 3]}, for all p, q, r ∈ Q, a ∈ Σ. A guess is then made