为字符串创建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屋!