增加结构非循环模糊自动机最小化算法(2006年)资源-CSDN文库

自然科学

论文

需积分: 8 30 浏览量 2021-05-18 09:53:54 上传评论收藏 313KB PDF 举报

资源推荐

资源详情

资源评论

CHINESE

JOURNAL

Aug.

2006

ENGINEERING

MATHEMATICS

Vo!.

No.

Article

ID:

1005-3085(2006)04-0599-ω

Incremental

Construction

Minimal

Acyclic

Deterministic

zzy

Finite

Automaton

Hong-li,

Zhi-wen

(College ofMathematics and Software Science

, Sichuan Normal University,

Che

吨

610066)

Abstract:

presented a new semi-incremental algorithm, which combines with properties of acyclic

deterministic fuzzy automata. Because the algorithm is related with fuzzy membership

present some novel functions which make the new algorithm

different

仕

general

algorithm.

can be applied to multi-incoming (transitions) states by applying build-

imitate state. So the new semi-incremental algorithm

more useful and practical. The new

algorithm

composed of two parts: adding fuzzy strings to minimal acydic deterministic

fuzzy finite

state

automata (ADFFAs) and minimizing the resulting automata. Because

some novel functions are applied in the algorithm

for

adding fuzzy stings

ADFFAs. The

resulting automaton of the algorithm

still deterministic and

not added more

than

one

fuzzy string to automaton.

Keywords:

acyclic deterministic fuzzy finite automaton; fuzzy strings; semi-incremental algorithm;

build-imitate state; unnecessary-membership

state

Classification:

AMS(2000) 68Q19

CLC

number:

T312

Document

code:

Introduction

zzy

set

theory

has

received considerable

attention

since

its

inception[1,

2j.

wide

飞

rariety

tools

have

been

developed

basing

the

notion

fuzzy

membership

function.

for

example

there

has

been

increased

interest

combing fuzzy

systems

with

finite

automata.

The

notion

fuzzy

automata

was

introduced

Lee

and

Wee[3,

4j.

80me

basic

properties

fuzzy

automata

can

found

，

，可.

As a design

tool

the

fuzzy

automata

should

best

, if

minima

this

也.p

，

present

two

algorithms

for

adding

fuzzy

strings

acyclic

deterministic

fuzzy finite

automata

(ADFFAs)

and

minimizing

the

resulting

automata

semi-incremental

techniques

，町咆

used

constrict

minimal

ADFFAs.

The

semi-incremental

algorithm

is used

minimal

condition

, so

named

semi-incrementa

This

was applied

some

papers[8,

but

these

papers

only considered

the

general

automata.

this

paper

order

constricting

minimal

acyclic

deterministic

fuzzy finite

state

automata

, we would combine

the

general

semi-incremental techniques

with

fuzzy

nature.

work

the

semi-incremental

algorithm

not

applicable

the

multi-incoming

(transitions)

stat

臼

(in

some

pap

町

they

are

named

confuse states)[lO-13j. Nevertheless,

the

multi-incoming

(transitions)

states

usually exist, especially

minimal

automata.

The

new

semi-incremental

algorithm

given

this

paper

can

applied

multi-incoming

(transitions)

states.

the

new

algorithm

general

and

easier

implement.

Received date:

200

4-0

12.

Biography:

Hongli

(Born

197η

，民

male

，

Master.

field:

fuzzy

theory,

rou

也

theory and

finite

automaton.

600

CHINESE

JOURNAL

ENGINEERING

MATHEMATICS

VOL.23

The

rest

the

paper

organized as follows. Some necessary

mathematical

preliminaries are

given in

the

section

a new algorithm for adding fuzzy strings

minimal acyclic deterministic

fuzzy finite

automata

(ADFFAs) is proposed

the

section

is described in detail

section 4

how

minimize

the

resulting

automata

(ADFFAs) from

the

algorithm for adding fuzzy strings

ADFFAs.

example of adding fuzzy strings

and

minimizing

the

resulting

automata

explained in

detail

the

section

Some remarks

are

finally given

section 6.

Mathematical

Preliminaries

this

article,

consider ADFFAs.

The

algorithm of

this

paper

is readily

extended

acyclic nondeterministic fuzzy finite

automata.

The

nondeterministic fuzzy finite

automata

are

more useful

than

the

deterministic fuzzy

automata

practice.

But

the

extension is

not

considered in

this

paper. We begin

defining

the

deterministic fuzzy

automata.

Definition

2.1

A deterministic fuzzy finite

state

automata

(DFFAS) is a

6-t

叩

DFFA=

~，

，

F), where Q is a

缸

lite

set

states

is a

缸lÏ

set

symbols called

the

alphabet

the

initial

state

, F ç Q is a

set

final

states

Q x

~→

the

state

transition

function

，

:Qx~

→

，

the

fuzzy

transition

function,

and

the

following conditions

are

satisfied:

for all

，

for all

ξ~

，

there

exists

p ε

such

that

8(q,

= p ,

then

，

> 0,

2) for all q E Q, for all

αε~

，

there

isμ

，

α)

> 0,

then

there

exists

p ε

such

that

8(q

，

)

The

extended

function

: Q x

~*→

defined as follows:

(6(qε)

εis

…

山

8*(q

，

= 8*(8(q, a),

, for all

αε~

and

x E

~*.

The

extended function

p,*

: Q x

~*→

，

is defined as follows:

(μ

ε)

1ε

叫

叫"

*(q

，

冲

叫

)^μ*

气

(θ

8(q

，

冲

叫)

, for all αε~

and

ε~*.

this

article, we consider a fuzzy

automaton

without

output

and

moreover

the

initial

state

and

the

set

final

states

are

not

fuzzy. Any fuzzy

automaton

described in Definition

2.1 is equivalent

a fuzzy automaton[3l.

Definition

2.2

A deterministic fuzzy finite

state

automata

(DFFA ) is a acyclic deter-

ministic fuzzy

automaton

(ADFFA

if for all

αε~

and

，

8(q

α.

Definition

2.3

Given a

ADFFA=(Q

，~，

，

，酌，

F),

the

fuzzy language accepted

rec-

ognized

ADFFA is denoted by L (ADFFA ) (we call

recognized by ADFFA ). L (ADFFA

)={(ω

，也

)1ωε2

飞

8*(qo

，

ω)ε

and

气

，

)=u

笋

Definition

ADFFA=(Q

，

旦，

，

F) is a complete ADFFA, if 8

and

μare

total

transition

functions.

Theorem

2.1

For a

ADFFA=(Q

，~，

，

，酌

，

there

exists a complete ADFFA*=(Q u

土，~，

，

，酌

，

where

...L

absorption

state

, such

that:

L(ADFFA

)=L

(ADFFA*)

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38628920

粉丝: 3
资源: 962

增加结构非循环模糊自动机最小化算法 (2006年)

最新资源

增加结构非循环模糊自动机最小化算法 (2006年)

杭电编译原理实验——有限自动机的确定化和最小化

上机实验2-3有限自动机的确定化和最小化）1

论文研究 - 模糊自动机联合在目标跟踪中的应用

基于细胞自动机的加密算法研究与应用

编译原理实验五：有穷自动机的确定化

论文研究-一种基于学习自动机的推荐算法改进.pdf

非线性系统手册源代码集合包括神经网络、混沌映射、元胞自动机、遗传算法、模糊逻辑等

元胞自动机的Java算法

不确定有限状态自动机的确定化

形式语言与自动机 CYK算法

编译原理实验 DFA的最小化 c++代码

NUAA南航 形式语言与自动机编程作业 RIJK算法.zip

AC 自动机算法

确定有限自动机和非确定有限自动机

AC自动机算法（Aho-Corasick 多模式匹配算法）

自动机理论，KMP算法等

有穷自动机的原理及应用

模糊自动机在电磁波识别中的应用.pdf

论文研究-确定型格值有限自动机的最小化.pdf

编译原理实验 C++编写 NFA的确定化和最小化源程序

后缀自动机算法代码 C++

大数据-算法-树自动机与模糊树自动机的代数性质.pdf

不确定的有穷自动机的确定化

非线性系统手册原书第5版混沌，分形，元胞自动机，遗传算法，基因表达式编程，支持向量机，小波，隐马尔可夫模型，模糊逻辑与C 、JAVA和SymbolicC 程序

非确定有限自动机的确定化

基于距离比较的AC自动机并行匹配算法.docx

有限自动机的多模式匹配算法

最新资源

NUAA南航形式语言与自动机编程作业 RIJK算法.zip