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
剩余631页未读，继续阅读
sinat_21954747
- 粉丝: 0
- 资源: 24
我的内容管理
展开
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器：工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析：故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化：二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法：Beta与Alpha测试详解
- 软件测试周期详解：从需求分析到维护测试
- CMMI模型详解：软件企业能力提升的关键
- 移动Web开发框架选择：jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
