Click here to Skip to main content
11,802,442 members (71,080 online)
Rate this: bad
Please Sign up or sign in to vote.
See more: C++ Java Perl
Hi guys
I am working on a project that my professor asked.
I need an algoritm to create a fsa for strings
takes this sentences: "ali goes to school"
and create a graph like this

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
Posted 17-Mar-13 13:45pm
Rate this: bad
Please Sign up or sign in to vote.

Solution 1

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

ali goes
ali goes to
ali goes home
ali goes to school


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

I hope this is helpful.
ali_crash at 18-Mar-13 13:41pm
yes it is helpful
which langueage you think I should use for programing project? C# or java?
Matthew Faithfull at 18-Mar-13 13:45pm
Personally I would use C# if those were the choices but if you know both then I don't think it makes any difference. Although it might be easier to get C# help on CodeProject than Java help which is worth considering.
Rate this: bad
Please Sign up or sign in to vote.

Solution 2

ali_crash at 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 :)

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

  Print Answers RSS
0 KrunalRohit 366
1 OriginalGriff 365
2 F-ES Sitecore 295
3 Afzaal Ahmad Zeeshan 230
4 CPallini 230
0 OriginalGriff 2,950
1 Maciej Los 1,910
2 KrunalRohit 1,862
3 CPallini 1,645
4 Richard MacCutchan 1,157

Advertise | Privacy | Mobile
Web02 | 2.8.151002.1 | Last Updated 17 Mar 2013
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100