Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Finite Automaton

by bravismore
on Oct 09, 2000 at 21:53 UTC ( #35970=perlquestion: print w/replies, xml ) Need Help??
bravismore has asked for the wisdom of the Perl Monks concerning the following question:

Write a Perl program which simulates the operation of finite automata. The finite automata are represented using transition tables. They are restricted to a maximum of 10 states labelled 0-9, with start state 0. Their alphabets are restricted to a maximum of 26 lower case symbols a-z. The alphabet and transition tables of the finite automaton are specified in blank-seperated fields. The first line specifies the alphabet of the finite automaton, representing end-of-strings as #. The next line represent the rows of the transition table in order. The error condition is represented as ! and the accept condition by *. The line specifying the last row of the transition table is followed by a blank line, followed by zero or more lines representing the input strings, one string per line. The program must read the alphabet, the transition table and the input strings and for each string it must print, on one line, “Accept” or “reject”, followed by the input string. Input strings containing illegal symbols not in the machine’s alphabet must be rejected. The report on the final string must be followed by one blank line. The following lines for example represent a 3-state finite automaton which accepts strings over the alphabet {a,b} which contain double-b, followed by strings to be analysed: a b # 0 1 ! 0 2 ! 1 2 * <blank line> aababa babbaab abaaabbaa bbx <blank line> Given this input your program must output the following results: Reject aababa Accept babbaab Accept abaaabbaa Reject bbx <blank line> The representations of zero or more finite automata and their strings are given in a file. The program must write output to a file.

Replies are listed 'Best First'.
Re: Finite Automaton
by rpilkey (Novice) on Dec 01, 2000 at 04:24 UTC
    This guy is missing out. I remember doing an assignment like this in my Theory of Computation class, for a Mealy Machine. What made it hard was that conditional statements were not allowed anywhere in the program. I spent a lot of skull sweat on that one. Once the light dawned on me, I understood the true meaning of a State Machine. It was wonderful. The result was less than 60 lines of C, but it was one of the most satisfying programs I have ever written.
Re: Finite Automaton
by rlk (Pilgrim) on Oct 09, 2000 at 22:54 UTC

    Look, if you want help with this, we'll be happy to give it. What we won't do is do it for you. Make an effort to solve the problem, and then come to us and show us what you've got and what you still need help with. Don't just copy and paste your homework assignment. We're not dumb, and the more times you try this, the less likely you are to get some help if you actually put some effort into it.

    Ryan Koppenhaver, Aspiring Perl Hacker
    "I ask for so little. Just fear me, love me, do as I say and I will be your slave."

Re: Finite Automaton
by merlyn (Sage) on Oct 09, 2000 at 22:05 UTC
Re (tilly) 1: Finite Automaton
by tilly (Archbishop) on Oct 09, 2000 at 22:02 UTC
    This looks like a rehash of RE: Sorry and I am voting -- on this one for the same reasons that I did that one.
Re: Finite Automaton
by AgentM (Curate) on Oct 09, 2000 at 23:28 UTC

      That's almost worth a ++

      <duck and cover>

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://35970]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2017-03-26 23:29 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (315 votes). Check out past polls.