Help w/ converting FSA to NFA program

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Willing 2 Learn

    #1

    Help w/ converting FSA to NFA program

    Below is a program I did to recognize a Finite State Automata for ASCII
    (J+H)*. I got that one working but im having trouble getting the NFA
    program to work. I really desperately need help!

    My NFA has initial states: 2 and 12
    ending states 2 and 12

    I need help to switch program below from FSA to recognize NFA. I was
    trying to do a general program so if i have another expression it can
    be easily changed thus no nested if-statements as I thought.

    I was thinking of having multiple arrays but wasn't quite sure how to
    include this.

    in this program, i want to:
    Enter 1 bit at a time
    list initial states
    list the first bit of input
    list the next states
    list the next bit of input
    list the next states
    repeat until my string is recognized or dead.

    Rules for my machine
    2 with 0 turns on 2,3,4,5,6,7,8,9 ,12
    3 with 1 turns on 2,4,5,6,7,8,9,1 2
    4 with 0 turns on 2,5,6,7,8,9,12
    5 with 0 turns on 2,6,7,8,9,12
    6 with 1 turns on 2,7,8,9,12
    7 with 0 turns on 2,8,9,12
    8 with 1 turns on 2,9,12
    9 with 0 turns on 2,12
    12 with 0 turns on 2,12,13,14,15,1 6,17,18,19
    13 with 1 turns on 2,12,14,15,16,1 7,18,19
    14 with 0 turns on 2,12,15,16,17,1 8,19
    15 with 0 turns on 2,12,16,17,18,1 9
    16 with 1 turns on 2,12,17,18,19
    17 with 0 turns on 2,12,19
    18 with 0 turns on 2,12,19
    12 with 0 turns on 2,12,





    #include <iostream.h>

    //(01001010 + 01001000)*

    int main()
    {
    int delta[10][2] = {
    {0,0}, //0
    {2,0}, //1
    {0,3},
    {4,0},
    {5,0},
    {0,6}, //5
    {7,0},
    {9,8}, //7
    {1,0}, //8
    {1,0} //9

    };
    int s, q, qi, qf; //qi= initial state qf-final state
    qi = 1; qf=1;
    q=qi;
    cout<<endl<<q;
    cin>>s;
    while(s < 2)
    {
    q = delta[q][s];
    cout<<endl<<q;
    cin>>s;
    } // end while
    if(q==qf)
    {
    cout<<"win";
    }
    else
    {
    cout<<"lose";
    }

    return 0;
    }

  • osmium

    #2
    Re: Help w/ converting FSA to NFA program

    "Willing 2 Learn" writes:
    [color=blue]
    > Below is a program I did to recognize a Finite State Automata for ASCII
    > (J+H)*. I got that one working but im having trouble getting the NFA
    > program to work. I really desperately need help![/color]

    I find your post very confusing. You wrote a program and got that one
    working. Fine.
    [color=blue]
    >
    > My NFA has initial states: 2 and 12
    > ending states 2 and 12
    >
    > I need help to switch program below from FSA to recognize NFA.[/color]

    What is this? Is this the program that you allege works?
    [color=blue]
    >I was
    > trying to do a general program so if i have another expression it can
    > be easily changed thus no nested if-statements as I thought.
    >
    > I was thinking of having multiple arrays but wasn't quite sure how to
    > include this.
    >
    > in this program, i want to:
    > Enter 1 bit at a time
    > list initial states
    > list the first bit of input
    > list the next states
    > list the next bit of input
    > list the next states
    > repeat until my string is recognized or dead.
    >
    > Rules for my machine
    > 2 with 0 turns on 2,3,4,5,6,7,8,9 ,12[/color]

    What does "turn on" mean? I see a list of numbers. Are they states? How do
    you "turn on" a state? You are in a state, you enter states, you leave
    states. "Turning on" is a foreign concept to me.
    [color=blue]
    > 3 with 1 turns on 2,4,5,6,7,8,9,1 2
    > 4 with 0 turns on 2,5,6,7,8,9,12
    > 5 with 0 turns on 2,6,7,8,9,12
    > 6 with 1 turns on 2,7,8,9,12
    > 7 with 0 turns on 2,8,9,12
    > 8 with 1 turns on 2,9,12
    > 9 with 0 turns on 2,12
    > 12 with 0 turns on 2,12,13,14,15,1 6,17,18,19
    > 13 with 1 turns on 2,12,14,15,16,1 7,18,19
    > 14 with 0 turns on 2,12,15,16,17,1 8,19
    > 15 with 0 turns on 2,12,16,17,18,1 9
    > 16 with 1 turns on 2,12,17,18,19
    > 17 with 0 turns on 2,12,19
    > 18 with 0 turns on 2,12,19
    > 12 with 0 turns on 2,12,
    >
    >
    >
    >
    >
    > #include <iostream.h>
    >
    > //(01001010 + 01001000)*[/color]

    ASCII is a seven bit ocde. I count 8 bits above.

    Is this true?

    JH ok
    JJJH ok
    J ng
    H ng
    JJHH ng
    A ng
    [color=blue]
    > int main()
    > {
    > int delta[10][2] = {[/color]

    Could you rename that to next_state without loss of clarity?
    [color=blue]
    > {0,0}, //0
    > {2,0}, //1
    > {0,3},
    > {4,0},
    > {5,0},
    > {0,6}, //5
    > {7,0},
    > {9,8}, //7
    > {1,0}, //8
    > {1,0} //9
    >
    > };
    > int s, q, qi, qf; //qi= initial state qf-final state[/color]
    [color=blue]
    > qi = 1; qf=1;[/color]

    I would expect a much larger value than 1 for qf.
    [color=blue]
    > q=qi;
    > cout<<endl<<q;
    > cin>>s;
    > while(s < 2)[/color]

    Are you happy with an input of -7?
    [color=blue]
    > {
    > q = delta[q][s];[/color]

    Do you have q and s inverted?
    [color=blue]
    > cout<<endl<<q;
    > cin>>s;
    > } // end while
    > if(q==qf)
    > {
    > cout<<"win";
    > }
    > else
    > {
    > cout<<"lose";
    > }
    >
    > return 0;
    > }[/color]

    It does not help that Google Net does not handle ASCII code properly. It
    treats TAB as though it were NUL. Get a real Usenet provider or else use
    explicit spaces, not tabs.


    Comment

    Working...