Click here to Skip to main content
Rate this: bad
good
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
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 14:45pm
Rate this: bad
good
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
 
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.
  Permalink  
Comments
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
good
Please Sign up or sign in to vote.

Solution 2

  Permalink  
Comments
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 OriginalGriff 587
1 Sergey Alexandrovich Kryukov 479
2 Maciej Los 305
3 BillWoodruff 220
4 Mathew Soji 195
0 OriginalGriff 7,356
1 Sergey Alexandrovich Kryukov 6,817
2 DamithSL 5,461
3 Manas Bhardwaj 4,946
4 Maciej Los 4,475


Advertise | Privacy | Mobile
Web01 | 2.8.1411023.1 | Last Updated 17 Mar 2013
Copyright © CodeProject, 1999-2014
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