Help w/ converting FSA to NFA program

  • Thread starter Willing 2 Learn
  • Start date
W

Willing 2 Learn

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,12
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,16,17,18,19
13 with 1 turns on 2,12,14,15,16,17,18,19
14 with 0 turns on 2,12,15,16,17,18,19
15 with 0 turns on 2,12,16,17,18,19
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];
cout<<endl<<q;
cin>>s;
} // end while
if(q==qf)
{
cout<<"win";
}
else
{
cout<<"lose";
}

return 0;
}
 
O

osmium

Willing 2 Learn said:
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!

I find your post very confusing. You wrote a program and got that one
working. Fine.
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.

What is this? Is this the program that you allege works?
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

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.
3 with 1 turns on 2,4,5,6,7,8,9,12
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,16,17,18,19
13 with 1 turns on 2,12,14,15,16,17,18,19
14 with 0 turns on 2,12,15,16,17,18,19
15 with 0 turns on 2,12,16,17,18,19
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)*

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
int main()
{
int delta[10][2] = {

Could you rename that to next_state without loss of clarity?
{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;

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

Are you happy with an input of -7?
{
q = delta[q];


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

return 0;
}

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top