为字符串创建FSA的算法 [英] an algoritm to create FSA for strings

问题描述

大家好

我正在研究一个我教授问过的项目。

我需要一个算法来为字符串创建一个fsa

例如：

用这句话：阿里去学校

并创建一个这样的图表

START-> ali-> go-> to-> school-> END



绘制这样的图表的图形部分并不重要。



问题是如何创建它。



这个项目是为了一个名为The Formal Languages&Automata的课程。 />
教授会从一个文本文件中获取一些字符串，并为它们绘制一个共同的fsa，这个文件中的所有字符串都可以用taht解析。



我需要一个认真的帮助。所以，请与我分享你的知识

谢谢。

Hi guys
I am working on a project that my professor asked.
I need an algoritm to create a fsa for strings
example:
takes this sentences: "ali goes to school"
and create a graph like this
START->ali->goes->to->school->END

the graphical part of drawing a chart like this is not important.

the question is how can I create this.

this project is for a lesson named "The Formal Languages & Automata".
Professor wnats a peogram that take some strings from a text file and draw a common fsa for them, a fsa that all of strings in that file can be parsed with taht.

I need a serious help. so please share your knowledge with me
thank.

推荐答案

现在你可能比这里的大多数人更了解这个在它的中间，这样你就可以得到一个更好的回应，当你遇到它并在遇到问题时询问更具体的问题。自从我看到这样的事情已经很长时间了，所以不要说任何事。鉴于此，如果我没记错的话，你可以通过为每个从第一个项目开始的独特子序列创建一个状态，然后根据潜在的状态转换数量从那里剔除来强制执行此操作。



阿里去学校

阿里回家



状态：

ali

阿里去了

阿里去了

阿里回家

阿里去学校



图：

START-> ali-> go-> to-> school-> END

- > ; home-> END



各种减少都是可能的，例如''ali''后面总是跟''去''只有一个可用的转换所以''ali ''可以成为一个州，类似''到学校''给出一个缩小的图表：

START->''ali goes'' - >''to school'' - >结束

- >''home'' - > END



我希望这有用。

Right now you probably know more about this than most people here as you''re in the middle of it so you may get a better response by having a go at it and asking more specific questions when you get stuck. It''s been a very long time since I looked at anything like this so don''t take my word for anything. Given that, IF I remember correctly you can brute force this by creating a state for every unique sub sequence that starts at a first item and then culling from there based on the number of potential state transitions.

ali goes to school
ali goes home

states:
ali
ali goes
ali goes to
ali goes home
ali goes to school

graph:
START->ali->goes->to->school->END
->home->END

Various reductions are possible for example ''ali'' is always followed by ''goes'' only one available transition so ''ali goes'' can become one state, similarly ''to school'' giving a reduced graph:
START->''ali goes''->''to school''->END
->''home''->END

I hope this is helpful.

尝试

http://fsa.sourceforge.net/ [ ^ ]

http://www.eti.pg.gda.pl/katedry/kiw/pracownicy/Jan .Daciuk / personal / minim.html [ ^ ]

这篇关于为字符串创建FSA的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！