an algoritm to create FSA for strings

Question

0.00/5 (No votes)

See more:

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.

Posted 17-Mar-13 13:45pm

ali_crash

Add a Solution

2 solutions

Solution 2

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

Posted 17-Mar-13 15:49pm

Abhinav S

Comments

ali_crash 18-Mar-13 13:39pm

I couldn't download that programs source and they are not exactly my problem's solution
please give me some codes, thanks :)

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Matthew Faithfull · Accepted Answer · 2013-03-17T14:06:00

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.