Finite automata to Regular Grammar with Thundax P-Zaggy
Moving ahead with FA, now we can generate the right-linear grammar that corresponds to the finite automata generated. The system is pretty simple and basically what the algorithm does is to go recursively through every state and to store the production (A → bC) using the info from the transition and both states.
P-Zaggy will use description text to assign unique variable names to each state. Each transition in the graph matches a production in the right-linear grammar. For example (right side image), the transition from “A” to “B” along the transition “a” matches the production “A → aB”. This production will be automatically added into the production list in the "Finite Automaton (simulation)" tab. To generate the full grammar, just open your finite automata and press "Get grammar" button to get the linear grammar. Now as any final state carries the production to λ, λ symbol has been added to the system as empty string.
In the following image you will see a general example with the automatically generated grammar:
Example with λ string:
Demo video:
Get the latest version from here:
- Thundax P-Zaggy v1.20 build 208. (Executable)
Looking back/ahead:
This would be the last post of the year 2011 and I'm taking this moment to review all the good stuff I have been publishing in my blog, from the physics engine to different code snippets and all of them with the help of a big an bright Delphi community. I always find difficult to get round to writing more often but I always have my notebook with me and every time and idea pops out I am there to catch it. I have an endless list of really interesting stuff I would like to tackle and I hope next year would be more fruitful as there are less than 50 articles for this year (even though the visits have been increased to almost 6K per month wow!, I am grateful for that!). I am also blissfully happy for putting grain of salt in the community as I have widely used the knowledge of others and it is great to pay back.
Next year I will be implementing different algorithms and I will be focusing on grammars, compilers and AI as I am very keen on those subjects and as you already know I like a lot visual stuff (And everything or almost everything with my loved Delphi). I'm preparing a roadmap about different utilities I have in mind and stay tuned for new and very interesting stuff!.
Happy new year 2012!.
Jordi Corbilla
Related links:
Happy 2012!
ReplyDelete