Nondeterministic Finite Automata in PHP

A few weeks ago, I wrote an article about an implementation of a DFA (deterministic finite automaton) in PHP. Today, I present a implementation for an automaton, that is not deterministic. It means, that the automaton have no, one or more than one edges (for an element from the input alphabet) to an other state. Before I start to give you a launch into how the NFA in PHP works, I give you a short introduction into the theory of nondeterministic finite automata.



style="display:block"
data-ad-client="ca-pub-2250494829484781"
data-ad-slot="4643133154"
data-ad-format="auto">


To demonstrate an easy example, I use a NFA, that accepts a word, which includes the substring ‘abc’. I used this example also in a previous article (about DFAs). You can compare the following automaton with the DFA that accepts the same words and you would come to the conclusion, that the NFA is easier to build. Thats the truth, but on the other hand, in most (not all) cases the NFA needs more time to execute all simultanous calculations for a token from the alphabet.

An automaton needs (for formal description) an input alphabet. For that example, the alphabet is specified as:

for this example:
Σ = {a,b,c}

A few sentences ago i mentioned, that the NFA needs more time to execute all simultanous calculations. But why? Well, let us choose the input word ‘ccababca’. (For further demonstrations I will use s1, s2, s3 and s4 as names for the states [blue circle] from the left to the right) We start the simulation with the first two tokens ‘cc’. The NFA remains in s1 (state 1). After that the NFA simulates for the token ‘a’. In s1 with input ‘a’ the NFA can go to s2 and can also stay in s1 (self-loop). Here we have the main problem! The NFA simulates all possible calculations and that is the problem, that the NFA has. After token ‘a’ comes token ‘b’ and for that token, the NFA simulates s1 and s3.

The PHP implementation of the NFA works with the transition table of every state. Outward from the starting state(s), the algorithm is looking for a transition from the current state to another – the successor state. After the input word was read, the NFA checks whether it is currently in a final state or not. The formalization of a final state is defined with a thicker border line (as you can see in the sketch above the text). In the PHP implementation it is just a boolean value. You can also choose more than one starting states with:

$nfa = new NFA('test_nfa');
//adding new states
//declare starting states
$nfa->setStartingStates(array('s0','s1'));

The function, explained below, is very important to build NFA’s – but not neccessary. In the code example below, we don’t need this function, therefore it has an own example above.

The code example shows the code fragment, that has the equal functionality as the automaton in the sketch.

require 'NFA.class.php';

$nfa = new NFA('test_nfa');

$s1 = new NFA_State('s1');
$s1->setTransition('b', 's1');
$s1->setTransition('c', 's1');
$s1->setTransition('a', 's2');
$s1->setTransition('a', 's1');
$nfa->setState($s1);

$s2 = new NFA_State('s2');
$s2->setTransition('b', 's3');
$nfa->setState($s2);

$s3 = new NFA_State('s3');
$s3->setTransition('c', 's4');
$nfa->setState($s3); 

$s4 = new NFA_State('s4');
$s4->setTransition('c', 's4');
$s4->setTransition('b', 's4');
$s4->setTransition('a', 's4');
$s4->setFinal(true);
$nfa->setState($s4);

$nfa->setStartingState('s1');

if($nfa->run('accbbababcababa'))
  echo "NFA accepts the input word!";
else
  echo "NFA doesn't accept the input word!";

As you can see in this example, the NFA equals a pattern matcher. With a regular expression parser you are able to build small NFA’s for every part of this expressions. After that you can concatenate this automatons to an automaton, that accepts your complete expression.



style="display:block"
data-ad-client="ca-pub-2250494829484781"
data-ad-slot="4643133154"
data-ad-format="auto">


You can download the source files here. (NFA.class.php, NFA_State.class.php and test.php)

135 thoughts on “Nondeterministic Finite Automata in PHP

  1. Candy says:

    Gone are the days of one way marketing or merely just posting comments about your site or other related topics.
    So what are you going to put in their search box is “website optimization tips”.

    But it is extremely important that anyone looking to
    hire an SEO professional be aware of the differences. A guy named Alan Emtage, a student at the University
    of Mc – Gill, developed the first search engine for the Internet in 1990.

  2. Erick says:

    Many small companies prefer to hire SEO specialists as consultants rather
    than full time employees, unless they have a certain amount of websites that need to be
    continuously maintained and optimized. Any business to conduct business on the web should have a web site created especially
    for creating an awareness of their products and ser-vices to the planet at
    large. But in general here are the services that an online business owner should expect from SEO experts and other agencies and consultants:.
    There are two techniques that combine to form a complete SEO.

  3. Nowadays, the conditions for your website to be ranked high in the search engine results are based on the search engine optimization techniques
    that you decide to use. Thirdly, the search engines need
    legit companies to do site optimization. Auro – IN has a strong team that
    is built on the delivery of outstanding campaign results,
    customer service and appreciation, and high levels of technical capabilities and values.
    Further the sites whose ranking using the search engines
    is good will attract potential clients, which results
    to mores sales.

  4. Marylyn says:

    Each of them has a different function according to the intensity of
    the misspelled keywords. Improving Site Structure – This second part tells you how to properly structure URLs.
    Depending on how how much time you have you can do this about once per week.

    In this way, it is informed about the kind of information that
    a surfer is looking for.

  5. Lincoln says:

    If your site is relatively sound, the most important results
    for you to consider are the keyword hits. Improving Site
    Structure – This second part tells you how to properly structure URLs.

    But it is extremely important that anyone looking to hire an SEO
    professional be aware of the differences. This
    mode of advertisement was faster than the earlier ones and reached more people but it had its own limitations.

  6. Marilynn says:

    Nowadays, the conditions for your website to be ranked high in the search engine results are based on the search engine optimization techniques that you decide to use.
    When Page – Rank was patented the patent was assigned to Stanford University.
    Unlike TV, radio and other traditional marketing channels that need big
    budgets to be effective, SEO can be cost effective. You have to take price quotes from different SEO companies
    locally and internationally.

  7. Camilla says:

    Gone are the days of one way marketing or merely just posting
    comments about your site or other related topics. So what are you going to
    put in their search box is “website optimization tips”. Auro – IN has a
    strong team that is built on the delivery of outstanding campaign results,
    customer service and appreciation, and high levels of technical capabilities
    and values. Eventbrite is an online party-planning tool with KISS (Keep It Simple Stupid)
    design so it is usually a top rated choice among
    event planners (organizers).

  8. You are so awesome! I do not believe I’ve truly read something like this before.
    So good to find somebody with some genuine thoughts on this
    subject. Seriously.. thank you for starting this up.
    This site is something that is needed on the web, someone
    with a bit of originality!

  9. Reginald says:

    Each of them has a different function according
    to the intensity of the misspelled keywords.

    When Page – Rank was patented the patent was assigned to Stanford
    University. Forgetting to write for an audience is one of the biggest mistakes that bloggers make.
    Further the sites whose ranking using the search engines is good
    will attract potential clients, which results to mores sales.

  10. Dominic says:

    Nowadays, the conditions for your website to be ranked high in the search engine results
    are based on the search engine optimization techniques
    that you decide to use. Thirdly, the search engines need
    legit companies to do site optimization. Auro – IN has a strong team that is
    built on the delivery of outstanding campaign results, customer service and
    appreciation, and high levels of technical capabilities and values.
    This mode of advertisement was faster than the earlier ones and reached more people but it had its own limitations.

  11. Hi there, I found your webste by means of Google whilst searching for a related topic, your site came up, it appears too be
    liie great. I have bookmarked it in myy google bookmarks.

    Hello there, just changed into aware of your blog thru Google, and located that it’s reaoly informative.
    I am going to be careful for brussels. I will appreciate should you proceed this in future.
    Numerous other people might be benefited from your writing.

    Cheers!

  12. You should be a part of a contest for one of the highest quality blogs
    on the net. I am going to highly recommend this blog!

  13. Maurice says:

    Sehr guter Artikel! Ich schaue mir sehr gerne Videos Online an. Vorallem mag ich Maxdome.

  14. Jaqueline says:

    Gone are the days of one way marketing or merely just posting comments about your site or other related topics.
    So what are you going to put in their search box is
    “website optimization tips”. But in general here are the services that an online business owner should expect from SEO experts and
    other agencies and consultants:. A reputable SEO company won’t have any
    qualms about connecting potential clients with former ones.

  15. Kelvin says:

    Gone are the days of one way marketing or merely just posting comments about your site
    or other related topics. The trends in this industry change and new developments take place only when Google comes up
    with some novel feature that ends up breaking
    every site’s SEO and compels them to consider a change in their current content
    presentation in order to do well. Your baseline will tell you where your company began so you can measure positive or
    negative ROI (return on your investment). There are two techniques that combine to form a complete SEO.

  16. Louis says:

    Get testimonials from the clients you already worked with, about your work and experiences.

    Improving Site Structure – This second part tells you
    how to properly structure URLs. Depending on how how much time you have you can do this
    about once per week. You have to take price quotes from different SEO companies locally and internationally.

  17. Magnificent beat ! I wish to apprentice even as you amen your site,
    how could i subscribe for a blog website? Thhe account helped me a
    acceptable deal. I were tiny bit familiar of this yohr broadcast offered vibrant clear concept

  18. All of the associates program you are signed up with, present particulars of plan/objects bought via your affiliate links.

  19. Many small companies prefer to hire SEO specialists
    as consultants rather than full time employees, unless they have a certain amount of websites that need to
    be continuously maintained and optimized. Any business
    to conduct business on the web should have a web site created especially for creating an awareness of their
    products and ser-vices to the planet at large.
    Thematic relevance is of key importance for the creation of quality backlinks.
    Eventbrite is an online party-planning tool with KISS (Keep
    It Simple Stupid) design so it is usually a top rated choice among event planners (organizers).

  20. Por servirnos de un ejemplo en el caso de la participación de equipos mexicanos afiliados a la CONCACAF en la Copa
    Libertadores de América, organizada por la CONMEBOL.

  21. I constantly emailed this web site post page to all my associates, because if like to read it next my links will too.

  22. Gone are the days of one way marketing or merely just posting comments about your site or other related
    topics. The Internet has changed the way we attain information forever and Google has been the
    main driving force and proponent behind this instant
    access to information. I am hoping to show you that I can help
    you achieve top rankings in the sites like I have
    for all my other clients. Further the sites whose ranking using the search engines is good will attract potential
    clients, which results to mores sales.

  23. Diana says:

    Gone are the days of one way marketing or merely just
    posting comments about your site or other related
    topics. The process of SEO is the series of steps that are undertaken to ensure that a website is visible among
    internet users to an optimal level. While effective SEO needn’t be difficult,
    it does take work. This mode of advertisement was faster than the earlier ones and reached more
    people but it had its own limitations.

  24. Bart says:

    Although Yahoo isn’t the biggest, or the highest ranking search engine on the internet, it is still one
    of the most essential, and if you want use search engine
    optimization and promotion as a main technique in your marketing
    arsenal, you unquestionably need to get listed here. When Page – Rank was patented the patent was assigned to
    Stanford University. While effective SEO needn’t be difficult, it does take work.

    You have to take price quotes from different
    SEO companies locally and internationally.

  25. Catalina says:

    Hiring accountants in Sheffield means you’ll be consistently in touch with them.
    Simply visit their website and click on the appropriate link.
    Examine this to a paper credit score card software which you send out by means of
    the US Publish Plade oof work.

  26. Magda says:

    If your site is relatively sound, the most important results for you to consider are the keyword hits.
    When Page – Rank was patented the patent was assigned to Stanford University.
    I am hoping to show you that I can help you achieve top rankings in the sites like I have for all my other clients.
    In this way, it is informed about the kind of information that a surfer
    is looking for.

  27. Another major difference between the two is that while PPC is a paid form of advertising, organic search
    engine optimization is absolutely free. So what are you going to
    put in their search box is “website optimization tips”. While effective SEO
    needn’t be difficult, it does take work. Webmaster
    follows a long process to promote a website in top search engines (Google, Yahoo and Bing).

  28. Wonderful, what a blog it is! This webpage presents useful facts
    to us, keep it up.

  29. check says:

    Many small companies prefer to hire SEO specialists as consultants rather
    than full time employees, unless they have a certain amount of
    websites that need to be continuously maintained and optimized.

    When Page – Rank was patented the patent was assigned to
    Stanford University. Forgetting to write for an audience is one of the biggest mistakes that bloggers
    make. This mode of advertisement was faster than the earlier ones and reached more people but it had its own limitations.

  30. It is not my first time to pay a visit this site, i am visiting thyis
    site dailly and obtain nice facts from here all the time.

  31. Hair loss can be a battle for most people who have it, it can be
    a sensitive issue and a lot of people out there are embarrassed to share
    with you it. Address those problems, and you also can turn bad hair days around.
    Where to buy biotin for hair growth Since the 1940s, inositol or myo-inositol has become
    advertised being a hair grower.

    The company uses 100% organic Olive and Grapeseed oils in all of the of
    their hairdressing products and provide both scented and fragrance free products; from shampoos to intense hair elixirs.
    Bananas are filled with silica that is certainly able
    to enhance hair thickness as well as make hair stronger and more
    durable.

  32. Hey There. Ӏ foᥙnd your blog սsing msn. This іs а very smartly ѡritten article.

    Ⅰ’ll bе sure tօ bookmark іt ɑnd сome baсk to
    reaⅾ mߋre of уour helpful info. Ꭲhanks for tҺe post.

    I’ll defіnitely comeback.

  33. Estuardo says:

    Hi, thanks for the example. How to convert a AFN to AFD with php?

    Thanks.

  34. It is not my first time to go to see this web site, i am browsing this web page dailly and get fastidious facts from here all the time.|

Leave a Reply

Your email address will not be published. Required fields are marked *