C++ program...almost completed just trying to work out bugs...help needed

Discussion in 'OT Technology' started by mrburner, Feb 23, 2004.

  1. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    this is basically a program that will convert an nfa to a dfa...knowing what these are or how to convert them really aren't that necessary though as we have an input file and what the output file should look like

    here is what the input file looks like

    trans 0 a 0
    trans 0 b 0
    trans 0 c 0
    trans 0 a 1
    trans 1 b 2
    trans 2 c 3
    trans 0 b 4
    trans 4 b 5
    trans 5 b 3
    trans 3 a 3
    trans 3 b 3
    final 3

    trans means its a transition state with the first number being the current state, the 2nd number being the next state and the letter being the character to make this transition (if you need further explanation, i can explain)


    now here is what the resulting output file should look like

    Enter input file name: NFA.txt
    Listing of DFA transitions as:
    Set of current states.
    Set of next states.
    On input symbol.

    0
    0 1
    a

    0
    0 4
    b

    0
    0
    c

    0 1
    0 1
    a

    0 1
    0 2 4
    b

    0 1
    0
    c

    0 4
    0 1
    a

    0 4
    0 4 5
    b

    0 4
    0
    c

    0 2 4
    0 1
    a

    0 2 4
    0 4 5
    b

    0 2 4
    0 3 final
    c

    0 4 5
    0 1
    a

    0 4 5
    0 3 4 5 final
    b

    0 4 5
    0
    c

    0 3
    0 1 3 final
    a

    0 3
    0 3 4 final
    b

    0 3
    0
    c

    0 3 4 5
    0 1 3 final
    a

    0 3 4 5
    0 3 4 5 final
    b

    0 3 4 5
    0
    c

    0 1 3
    0 1 3 final
    a

    0 1 3
    0 2 3 4 final
    b

    0 1 3
    0
    c

    0 3 4
    0 1 3 final
    a

    0 3 4
    0 3 4 5 final
    b

    0 3 4
    0
    c

    0 2 3 4
    0 1 3 final
    a

    0 2 3 4
    0 3 4 5 final
    b

    0 2 3 4
    0 3 final
    c



    obviously it describes at the top what each part of this is

    now where i am right now...this is what my output file looks like

    0
    0 1
    a

    0
    0 4
    b

    0
    0
    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0
    0
    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0
    0
    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    0
    0 1
    a

    0
    0 4
    b

    0

    c

    obviously it just keep repeating itself...i know i'm just missing a few small things in my code but i can't figure out exactly what...parts of it are implemented in my "a" vectors but not in "b" or "c" because i'm just testing it out for now...the only transitions we can use are a, b, c and we can have a total of 6 states (0-5)



    now here is my code...if you might be able to tell me what is wrong w/ it, or give me what you think might be wrong with it, it would be much appreciated (the code is pretty complex...took me hours just to think about the logistics)...i went in and talked to my teacher about it today and she showed me her code which is much longer and very different (she uses a vector of bool's and for every possible current state she will have this vector of bools read true or false for each of the 6 states...she then makes the "true" states into the future current states and tests a, b, c with those...basically it was pretty confusing and very complex...i feel like my code should work

    anyways, any help is appreciated...thanks in advance


    #include <iostream.h>
    #include <fstream>
    #include <iomanip.h>
    #include <stdlib.h>
    #include <string>
    #include <vector>
    #include <stdio.h>

    using namespace std;

    int main()
    {


    char file_name[300];
    string states;
    int t1;
    int t2;
    char ch;

    vector <string> stateV;
    vector <int> t1V;
    vector <int> t2V;
    vector <char> chV;
    vector <int> finalV;
    vector <int> aCurrV;
    vector <int> aNextV;
    vector <int> bCurrV;
    vector <int> bNextV;
    vector <int> cCurrV;
    vector <int> cNextV;

    fstream infile;
    ofstream outfile ("out.txt");
    //user input for the input file
    cout << "Please enter the name and path of the input file: ";
    cin >> file_name;
    infile.open(file_name);

    while(!infile.eof())
    {
    infile >> states;
    if(infile.eof())
    {
    break;
    }
    else if(states == "trans")
    {
    infile >> t1 >> ch >> t2;
    stateV.push_back(states);
    t1V.push_back(t1);
    t2V.push_back(t2);
    chV.push_back(ch);
    }
    else if(states == "final")
    {
    infile >> t1;
    finalV.push_back(t1);
    }
    }
    infile.close();
    int i = 0;
    int j = 0;
    int k = 0;
    aCurrV.push_back(0);
    bCurrV.push_back(0);
    cCurrV.push_back(0);
    for(int k = 0; k < stateV.size(); k++)
    {
    for(int x = 0; x < chV.size(); x++)
    {
    if(t1V[x] == aCurrV && chV[x] == 'a')
    {
    for(int i = 0; i < aCurrV.size(); i++)
    {
    aNextV.push_back(t2V[x]);
    }
    }
    }

    for(int z = 0; z < aCurrV.size(); z++)
    {
    outfile << aCurrV[z] << " ";
    }
    outfile << endl;
    for(int z = 0; z < aNextV.size(); z++)
    {
    outfile << aNextV[z] << " ";
    }
    for(int z = 0; z < aNextV.size(); z++)
    {
    for(int i = 0; i < finalV.size(); i++)
    {
    if(aNextV[z] == finalV)
    {
    outfile << "final";
    }
    }
    }
    outfile << endl << "a" << endl << endl;
    int x = 0;
    for(int z = 0; z < aCurrV.size(); z++)
    {
    if(aCurrV[z] != aNextV[x])
    {
    aCurrV.push_back(aNextV[x]);
    x++;
    }
    else if(aCurrV[z] == aNextV[x])
    {
    x++;
    }


    }
    aNextV.clear();



    for(int x = 0; x < chV.size(); x++)
    {
    if(t1V[x] == bCurrV[j] && chV[x] == 'b')
    {
    for(int j = 0; j < bCurrV.size(); j++)
    {
    bNextV.push_back(t2V[x]);
    }
    }
    }

    for(int z = 0; z < bCurrV.size(); z++)
    {
    outfile << bCurrV[z] << " ";
    }
    outfile << endl;
    for(int z = 0; z < bNextV.size(); z++)
    {
    outfile << bNextV[z] << " ";
    }
    for(int z = 0; z < bNextV.size(); z++)
    {
    for(int i = 0; i < finalV.size(); i++)
    {
    if(bNextV[z] == finalV)
    {
    outfile << "final";
    }
    }
    }
    outfile << endl << "b" << endl << endl;
    int r = 0;
    for(int z = 0; z < bCurrV.size(); z++)
    {
    while(bCurrV[z] != bNextV[r])
    {
    bCurrV.push_back(bNextV[r]);
    r++;
    }
    }
    bNextV.clear();





    for(int x = 0; x < chV.size(); x++)
    {
    if(t1V[x] == cCurrV[k] && chV[x] == 'c')
    {
    for(int k = 0; k < cCurrV.size(); k++)
    {
    cNextV.push_back(t2V[x]);
    }
    }
    }

    for(int z = 0; z < cCurrV.size(); z++)
    {
    outfile << cCurrV[z] << " ";
    }
    outfile << endl;
    for(int z = 0; z < cNextV.size(); z++)
    {
    outfile << cNextV[z] << " ";
    }
    for(int z = 0; z < cNextV.size(); z++)
    {
    for(int i = 0; i < finalV.size(); i++)
    {
    if(cNextV[z] == finalV)
    {
    outfile << "final";
    }
    }
    }
    outfile << endl << "c" << endl << endl;
    int t = 0;
    for(int z = 0; z < cCurrV.size(); z++)
    {
    while(cCurrV[z] != cNextV[t])
    {
    cCurrV.push_back(cNextV[t]);
    t++;
    }
    }
    cNextV.clear();
    }
    }
     
  2. uneek

    uneek OT Supporter

    Joined:
    Dec 14, 2003
    Messages:
    12,002
    Likes Received:
    0
    Please explain what the program is actually supposed to do.
     
  3. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    Write a program called nfaTodfa.cpp that converts an NFA to a DFA. Your program will read the description of an
    NFA from a file and will output (to standard out) a description of an equivalent DFA. All final states should be
    annotated in your output report.
    Your program will receive the NFA input from a file. The file will be formatted exactly as in the previous
    assignment. To simplify the problem somewhat you may assume that the NFA has at most 6 states and 20 transitions
    with no epsilon transitions. The start state is 0. The alphabet for the NFA is {a, b, c}. The format for the output DFA
    will be identical to the input format of the NFA. However, your output automaton must have exactly one transition
    from each state on each input symbol.
     
  4. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    thats the description she gave us along with the input file and the output file for that input file...my program should read in the input file given and create a new output file (mine is called out.txt) that looks like her output file
     
  5. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
  6. mrburner

    mrburner Ron Paul 2008

    Joined:
    May 9, 2001
    Messages:
    7,448
    Likes Received:
    0
    Location:
    Phoenix
    i think the problem lies within this

    int x = 0;
    for(int z = 0; z < aCurrV.size(); z++)
    {
    if(aCurrV[z] != aNextV[x])
    {
    aCurrV.push_back(aNextV[x]);
    x++;
    }
    else if(aCurrV[z] == aNextV[x])
    {
    x++;
    }


    }
    aNextV.clear();


    because that should be setting new current states which should in turn be setting new next states each time the loop goes around but since it keeps repeating, i can only assume that it isn't doing any of this
     

Share This Page