匿名
匿名 發問於 電腦與網際網路程式設計 · 2 月前

請問用C++怎麼寫出finite state machine minimization 的程式?

如題,我想打出可以輸入想要的finite state machine(未化簡)數量,還要輸入input和output的數量,和需要列出全部的state,和state table,並且所有輸入和輸出都是從txt檔匯入,請問該怎麼做,如果可以,請告訴我程式碼會比較容易理解

2 個解答

評分
  • 1 月前

    An FSM can be defined as a list of state transition rules in the following format:

    StateX InputY OutputZ StateA

    where

    InputY belongs to a finite set of alphabets; and

    StateX StateA belong to a finite set of states; and

    There is no duplicate rules with the same <StateX, InputY>

    #include<iostream>

    #include<iomanip>

    #include<fstream>

    #include<string>

    #include<map>

    using namespace std;

    struct Rule{

      string state;

      string inout;

      Rule(const decltype(state)&s, const decltype(inout)&i):

        state(s),

        inout(i){}

      Rule(){}

      bool operator()(const Rule&a, const Rule&b) const {

        return a.state != b.state

             ? a.state  > b.state

             : a.inout  > b.inout;

      }

    };

    map<Rule,Rule,Rule> *readFSM(

      string fileName

    ){

      ifstream ifile(fileName);

      decltype(Rule::state) st0, st1;

      decltype(Rule::inout) in0, out1;

      auto*ret = new map<Rule,Rule,Rule>();

      auto stLen = st0.length(), alLen = in0.length();

      for(

         ; ifile >> st0 >> in0 >> out1 >> st1

         ;){

        Rule r0(st0, in0);

        if(st0.length() > stLen) stLen = st0.length();

        if(in0.length() > alLen) alLen = in0.length();

        if(ret->find(r0) == ret->end()){

          (*ret)[r0] = Rule(st1,out1);

          if(st1 .length() > stLen) stLen = st1.length();

          if(out1.length() > alLen) alLen = out1.length();

        }

      }

      ifile.close();

      if(stLen+alLen >= MinLen) MinLen = stLen+alLen+1;

      return ret;

    }

    int main(

      int argc,

      char*argv[]

    ){

      cout << "FSM is defined in file: " << argv[1] << endl;

      cout << "state transition run input is in file: " << argv[2] << endl << endl;

      auto*fsm{readFSM(argv[1])};

      map<decltype(Rule::state), int> stateMap;

      map<decltype(Rule::inout), int> alphaMap;

      for(auto&kk: *fsm){

        if(stateMap.find(kk.first.state) == stateMap.end())

          stateMap[kk.first.state] = 1;

        else

          ++stateMap[kk.first.state];

        if(alphaMap.find(kk.first.inout) == alphaMap.end())

          alphaMap[kk.first.inout] = 1;

        else

          ++alphaMap[kk.first.inout];

      }

      // print states

      cout << "State count: " << stateMap.size() << endl;

      for(auto&ss: stateMap) cout << "State: " << ss.first << " " << ss.second << endl;

      cout << endl;

      // print alphabets

      cout << "Alphabet count: " << alphaMap.size() << endl;

      for(auto&ss: alphaMap) cout << "Alpha: " << ss.first << " " << ss.second << endl;

      cout << endl;

      cout << "State Table" << endl;

      cout << setw(MinLen+2) << "State/input";

      for(auto&x: alphaMap) cout << setw(MinLen+2) << x.first;

      cout << endl;

      for(auto&s: stateMap){

        cout << setw(MinLen+2) << s.first;

        for(auto i: alphaMap){

          auto r0{Rule(s.first, i.first)};

          auto it = fsm->find(r0);

          decltype(r0.state) s0{"<"};

          if(it != fsm->end()) s0 += it->second.inout + "/" + it->second.state;

          s0 += ">";

          cout << setw(MinLen+2) << s0;

        }

        cout<<endl;

      }

      cout << endl;

      ifstream run(argv[2]);

      decltype(Rule::state) st0;

      decltype(Rule::inout) in0;

      cout << "State transitions: " << endl;

      for( run >> st0

         ; run >> in0

         ; ){

         auto it = fsm->find(Rule(st0,in0));

         if(it != fsm->end())

           cout << "@state=" << st0 << " input " << in0 << " output " << it->second.inout

                << " and transit to state " << (st0 = it->second.state) <<  endl;

         else

           cout << "@state=" << st0 << " received bad input " << in0 << ". Action/transition undefined."

                << endl;

      }

     

      cout << endl << endl << "The final state is " << st0 << endl;

      if(fsm) delete fsm, fsm = NULL;

      if(run.is_open())run.close();

      return 0;

    }

    $ g++ -std=c++11 -Wall -O3 fsm.cpp -o fsm

    $ ./fsm FSM.txt RUN.txt

    FSM file is

    FSM.txtinput file is RUN.txt

    State count: 3

    State: state0 2

    State: state1 1

    State: state2 2

    Alphabet count: 2

    Alpha: a 3

    Alpha: b 2

    State Table

            State/input               a               b

              state0      <A/state1>      <B/state2>

              state1      <a/state2>              <>

              state2      <X/state2>      <X/state2>

    State transitions:

    @state=state2 input a output X and transit to state state2

    @state=state2 input a output X and transit to state state2

    @state=state2 input b output X and transit to state state2

    @state=state2 input b output X and transit to state state2

    @state=state2 input b output X and transit to state state2

    @state=state2 input a output X and transit to state state2

    @state=state2 input b output X and transit to state state2

    @state=state2 input a output X and transit to state state2

    Qstate=state2 received bad input C. Action/transition undefined.

    @state=state2 input a output X and transit to state state2

    The final state is state2

    $

還有問題嗎?立即提問即可得到解答。