Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

finite automata

by Anonymous Monk
on Oct 02, 2001 at 13:59 UTC ( #116088=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

hie all , lam supposed to be writing a program in perl that validates whether a given string belongs to a set of a language , the language is the set of strings over the alphabet {a..z} , well looking for some help because lam stuck

Replies are listed 'Best First'.
Sibling - Make Nicer Post!
by George_Sherston (Vicar) on Oct 02, 2001 at 14:38 UTC
    Hey, Anonymous Monk, I fear this post is doomed. But it need not have been so. I think you would have got a lot of constructive answers if (A) you'd taken the trouble to get a user name and tell us a little bit about yourself (B) you'd specified the problem in a little more detail (C) you'd shown some of the efforts you'd made to solve it on your own.

    If you want answers, you're posting in the right place. I think most monks are fully seized of the dictum that it is more blessed to give than to receive, and there is a real zest for helping out round here, as I know very well from happy experience. But it's only polite, as well as wise, to make a little effort with one's question. Then a wealth of knowledge awaits you. And sooner or later you'll find a question you can answer, which will be even more fun.

    Perlmonks really is a community - treat it that way and it'll work wonders for you.

    </PREACH>

    George Sherston
Re: finite automata
by clemburg (Curate) on Oct 02, 2001 at 16:05 UTC

    Sorry, I could not resist ...

    fsm.pl:

    #!/usr/bin/perl -w use strict; my $config = do(shift || "fsm.config"); my $state = $config->{start_state}; my $input = ""; while (($state, $input) = compute($state, get_input())) { action($state, $input); } action($state, $input); # -------------------------------------------------- # subs # -------------------------------------------------- sub get_input { print "Your input (", join("|", @{$config->{input_alphabet}}), "): + "; my $input = <>; chomp($input); return $input; } sub compute { my ($state, $input) = @_; return $config->{transition_function}->{$state}->{$input}, $input; } sub action { my ($state, $input) = @_; $config->{action_function}->{$state}->{$input}->() if $config->{action_function}->{$state}->{$input}; die "REJECT\n" unless $state; die "ACCEPT\n" if accept_p($state); } sub accept_p { my ($state) = @_; return 1 if grep {$state eq $_} @{$config->{goal_states}}; return 0; }

    fsm.config:

    # template: # # my $config = { # states => [], # input_alphabet => [], # transition_function => { # "state" => { # "input" => "state", # "input" => "state", # }, # "state" => { # "input" => "state", # "input" => "state", # }, # }, # action_function => { # "state" => { # "input" => sub {}, # "input" => sub {}, # }, # "state" => { # "input" => sub {}, # "input" => sub {}, # }, # }, # start_state => "", # goal_states => [], # }; my $config = { states => [ "q0", "q1", "halt" ], input_alphabet => [ "a", "b", "#" ], transition_function => { "q0" => { "a" => "q0", "b" => "q1", }, "q1" => { "b" => "q1", "#" => "halt", }, }, action_function => { "q0" => { "a" => sub {print "q0 - +> q0\n"}, "b" => sub {print "q0 - +> q1\n"}, }, "q1" => { "b" => sub {print "q1 - +> q1\n"}, "#" => sub {print "q1 - +> halt\n"}, }, }, start_state => "q0", goal_states => [ "halt" ], };

    Christian Lemburg
    Brainbench MVP for Perl
    http://www.brainbench.com

Re: finite automata
by pjf (Curate) on Oct 02, 2001 at 14:23 UTC
    So... you want to tell whether or not a string is composed entirely of the alphabet a-z? That's pretty easy with a regexp.
    if ($string =~ /^[a-z]+$/) { print "Valid\n"; } else { print "Invalid\n"; }
    You mentioned finite automata in your subject line, though. Am I missing something else here? ;)

    Cheers,
    Paul

Re: finite automata
by doc (Scribe) on Oct 02, 2001 at 15:43 UTC

    This will get you started:

    #!/usr/bin/perl -w use strict; my $string = 'just another perl hacker'; # generate a lookup hash containing the words in our language # as the keys, we set the values to 1 with the ++ syntax # so as to define the keys which are all we use my %lang; do{ chomp; $lang{$_}++ }for <DATA>; # split the test string on whitespace to give us an # array that will contain all the 'words' where a # word is a character sequence my @bits = split /\s/, $string; # iterate over our word array seeing if they are # defined in our langugue specification for (@bits) { die "Word '$_' not in language!\n" unless defined $lang{$_}; } # if we have not died then all the words are OK print "Success, \$string only contains words in language!\n"; __DATA__ just another finite automaton perl hack

    doc

    print(s<>ecode?scalar reverse :p)

      I may, of course, be misunderstanding the problem, but it sounds to me like you're not given a complete listing of the language dictionary - simply a set of rules that valid words must obey. In that case pjf's regex-based solution is far more efficient (assuming, of course, that you can represent each of the rules as a regex).

      --
      <http://www.dave.org.uk>

      "The first rule of Perl club is you don't talk about Perl club."

        As you note it does rather depend on what the problem is. Depending on the situation and the complexity of the language a pre-generated hash lookup table will be potentially much faster than a regex solution.

        Consider a simple alphabet that may only contain words in the form: aa ab ac ad .... az. Including the overhead of generating the hash lookup table the hash method is much faster than a comparable regex method as well as being far more flexible.

        use Benchmark; $string = 'aa ab ac ad ae af ' x 10000 . ' ff'; @string = split /\s/, $string; $regex = <<'CODE'; &regex; sub regex { do{return 0 unless /^a[a-z]$/} for @string; return 1; } CODE $hash = <<'CODE'; $hash{$_}++ for aa..az; &hash; sub hash { do{return 0 unless defined $hash{$_}} for @string; return 1; } CODE timethese ( 100, { 'regex' => $regex, 'hash' => $hash } ); __END__ Benchmark: timing 100 iterations of hash, regex... hash: 21 wallclock secs (20.37 usr + 0.00 sys = 20.37 CPU) @ 4 +.91/s (n=100) regex: 45 wallclock secs (45.10 usr + 0.00 sys = 45.10 CPU) @ 2 +.22/s (n=100)

        doc

        print(s??cod??scalar reverse :p)

Re: finite automata
by demerphq (Chancellor) on Oct 02, 2001 at 17:48 UTC
    Homework Alert!

    Yves
    --
    You are not ready to use symrefs unless you already know why they are bad. -- tadmc (CLPM)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://116088]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2019-06-25 03:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Is there a future for codeless software?



    Results (101 votes). Check out past polls.

    Notices?