To simulate a TG(Transition Graph) I defined a data file format that can represe

Question

To simulate a TG(Transition Graph) I defined a data file format that can represent these. Here it is:

Write C++ code that can run against such an input file and simulate the TG action, printing each string and either accepting or rejecting it. You can useea3b.tg as an input file to test against. It does the regular expression (aa)*bbb, that is any string of a's and b's starting with an even number of a's and ending with 3 b's. This file is in Linux/Unix format, that is each line ends with only a line feed, not CRLF like in Windows. So if you download this file to use in DOS/Windows, you need to edit the file (as in "edit ea3b.tg") from a command prompt, then save the file on top of itself. That will make it be in CRLF format like DOS/Windows likes. Believe me if you don't do this you will get surprising output! (Note if you are using Win7 64 bit, edit will not exist. So use Notepad in that case).

Explanation / Answer

table.h

#ifndef TABLE_H
#define TABLE_H

struct Table_Entry
{
    unsigned int current_state_id;
    unsigned char transition_letter;
    unsigned int next_state_id;
};

Table_Entry const *    table_begin(void);
Table_Entry const *    table_end(void);

#endif // TABLE_H

table.cpp:

#include "table.h"

static const Table_Entry    my_table[] =
{
    // Current   Transition     Next
    // State ID    Letter     State ID
    {    0,          'A',        1}, // From 0 goto 1 if letter is 'A'.
    {    0,          'B',        2}, // From 0 goto 2 if letter is 'B'.
    {    0,          'C',        3}, // From 0 goto 3 if letter is 'C'.
    {    1,          'A',        1}, // From 1 goto 1 if letter is 'A'.
    {    1,          'B',        3}, // From 1 goto 3 if letter is 'B'.
    {    1,          'C',        0}, // From 1 goto 0 if letter is 'C'.
};

static const unsigned int TABLE_SIZE =
    sizeof(my_table) / sizeof(my_table[0]);

Table_Entry const *
table_begin(void)
{
    return &my_table[0];
}

Table_Entry const *
table_end(void)
{
    return &my_table[TABLE_SIZE];
}

state_machine.cpp

#include "table.h"
#include <iostream>

using namespace std;

void
Execute_State_Machine(void)
{
    unsigned int current_state = 0;
    while (1)
    {
        char transition_letter;
        cout << "Current state: " << current_state << " ";
        cout << "Enter transition letter: ";
        cin >> transition_letter;
        cin.ignore(1000, ' ');
        Table_Entry const * p_entry = table_begin();
        Table_Entry const * const p_table_end = table_end();
        bool state_found = false;
        while ((!state_found) && (p_entry != p_table_end))
        {
            if (p_entry->current_state_id == current_state)
            {
                if (p_entry->transition_letter == transition_letter)
                {
                    cout << "State found, transitioning"
                         << " from state " << current_state
                         << ", to state " << p_entry->next_state_id
                         << " ";
                    current_state = p_entry->next_state_id;
                    state_found = true;
                    break;
                }
             }
             ++p_entry;
         }
         if (!state_found)
         {
             cerr << "Transition letter not found, current state not changed. ";
         }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.