Automatô a Pilha (Trabalho: Programa de reconhecimento de linguagem)

Automatô a Pilha (Trabalho: Programa de reconhecimento de linguagem)

Instruções para leitura e gravagem de arquivos

Leitura de arquivo:

Código:

#include <iostream>
#include <fstream>//Bilioteca para leitura e escrita de arquivos
#include <string>
using namespace std;
using std::ifstream;//Função de abertura de arquivo;

const int lin=100, col=100;

int le_regra(char regras[lin][col], int regra);//Le o arquivo regra.txt
int le_palavras(char palavras[lin][col], int palavra);//Le o arquivo palavra.txt
void calc_sizechar(char matriz[lin][col], int marcador_de_fim);

void main()
{
   char regras[lin][col], palavras[lin][col];
   int regra=0, l, palavra=0;

   cout<< "Os arquivos devem estar na pasta C:>LFA>regra.txt\ne C:>LFA>palavras.txt, e nao devem ter mais que "<< lin << " Linhas \n\n" << "Os aquivos ja estao na pasata solicitada\ne tambem com os nome solicitados?\n\n";
   system("pause");

   system("cls");
   regra=le_regra(regras, regra);//Chama a função de leitura do aquivo regras.txt
   cout<< "=======================================\n" << "\t\tRegras\n" << "=======================================\n" ;
   for(l=0; l<regra; l++)//Percorre todos os indices de linha da matriz regras, até antes do seu ultimo indice vazio que é o indice regra
      cout<< regras[l] << endl;
   cout<< "\n\n";

   calc_sizechar(regras, regra);

   cout<< "\n\n";

   palavra=le_palavras(palavras, palavra);//Chama a função de leitura do aquivo palavras.txt
   cout<< "=======================================\n" << "\t\tPalavras\n" << "=======================================\n" ;
   for(l=0; l<palavra; l++)//Percorre todos os indices de linha da matriz palavras, até antes do seu ultimo indice vazio que é o indice palavra
      cout<< palavras[l] << endl;
   cout<< "\n\n";
   
   calc_sizechar(palavras, palavra);

   cout<< "\n\n";

   system("pause");
}

int le_regra(char regras[lin][col], int regra)
{
   char getchar[col];

   ifstream inregra("C:\\LFA\\regra.txt", ios::in);// Função de abertura de arquivo

   if( !inregra )// Verifica se o arquivo foi aberto com sucesso
   {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de regra.txt\n\n";
      exit(1);
   }

   while(inregra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
   {
      strcpy_s(regras[regra], getchar);//Copia o valor do vetor getchar para a linha da matriz regras no indice regra.
      regra++;// passa para o proximo indice
   }
   return regra;//retorna a ultima linha (indice da linha) livre da matriz regras
}

int le_palavras(char palavras[lin][col], int palavra)
{
   char getchar[col];

   ifstream inpalavra("C:\\LFA\\palavra.txt", ios::in);// Função de abertura de arquivo

   if( !inpalavra )// Verifica se o arquivo foi aberto com sucesso
   {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de palavra.txt\n\n";
      exit(1);
   }

   while(inpalavra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
   {
      strcpy_s(palavras[palavra], getchar);//Copia o valor do vetor getchar para a linha da matriz palavras no indice palavra.
      palavra++;// passa para o proximo indice
   }
   return palavra;//retorna a ultima linha (indice da linha) livre da matriz palavras
}

void calc_sizechar(char matriz[lin][col], int marcador_de_fim)
{
   int l, size;

   for(l=0; l<marcador_de_fim; l++)
   {
      size=strlen(matriz[l]);
      cout<< "A linha " << l+1 << " possui " << size << " caracteres\n";
   }
}

Regras para o Programa funcionar corretamente.

Linha 1: estados
Linha 2: alfabeto
Linha 3: alfabeto da pilha
Linha 4: estado inicial
Linha 5: estados finais

Deve seguir o modelo abaixo:

q0,q1,q2
a,b
X,Y
q0
q2

Linha 6 em diante: produções na forma

Deve seguir o modelo abaixo:
(q0,a,?):=(q0,X)
(q0,a,-):=(q0,X)
(q0,b,X):=(q1,Y)
(q1,b,-):=(q1,Y)
(q1,a,Y):=(q2,-)
(q2,a,Y):=(q2,-)
(q2,b,X):=(q2,-)

Regras para a linha 6 em diante:

Todas as possibilidades do mesmo estado devem estar agrupadas, ou seja uma após a outra como segue, (q0, ... .

Correto:

(q0,a,?):=(q0,X)
(q0,a,-):=(q0,X)
(q0,b,X):=(q1,Y)
(q1,b,-):=(q1,Y)
(q1,a,Y):=(q2,-)
(q2,a,Y):=(q2,-)
(q2,b,X):=(q2,-)

Incorreto:

(q0,a,?):=(q0,X)
(q1,b,-):=(q1,Y)
(q0,a,-):=(q0,X)
(q0,b,X):=(q1,Y)
(q2,b,X):=(q2,-)
(q1,a,Y):=(q2,-)
(q2,a,Y):=(q2,-)

Programa: Automato a pilha


Para testar o automato pode utilizar as seguintes regras e palavras

Código:

#include <iostream>
#include <fstream>//Bilioteca para leitura e escrita de arquivos
#include <string>
#include <stdlib.h>
using namespace std;
using std::ifstream;//Função de abertura de arquivo;

const int lin=100, col=100;

struct dynamic_vet
        {
            char info;
            dynamic_vet *prox;
        };

typedef struct dynamic_vet dynamic;

int le_regras(char regras[lin][col], int regra);//Le o arquivo regra.txt
int le_palavras(char palavras[lin][col], int palavra);//Le o arquivo palavra.txt
void mostra(char matriz[lin][col], int marcador_de_fim, int indicador);//Mostra toda a matriz que possui dados
//void calc_sizechar(char matriz[lin][col], int marcador_de_fim);//Conta quantos caracteres tem em cada linha
int menu(char regras[lin][col],int regra, char palavras[lin][col], int palavra);
dynamic *start();//Inicializa um vetor dinamico
dynamic *request_new(dynamic *vet);
dynamic *remove(dynamic *vet);
int getline_state(char regras[lin][col],int regra, int state);
bool check_line(char regras[lin][col],int regra, char palavras[lin][col], int palavra, int line);//Compara a liguagem da linha escolhida, seguindo as regras, e retorna verdadeiro ou falso
bool valida(dynamic *pilha, char val);

void main()
{
  char regras[lin][col], palavras[lin][col];
  int regra=0, palavra=0, op, line;
  bool result;

  cout<< "Os arquivos devem estar na pasta C:>LFA>regra.txt\ne C:>LFA>palavra.txt, e nao devem ter mais que "<< lin << " Linhas \n\n" << "Os aquivos ja estao na pasata solicitada?\ne tambem com os nome solicitados?\n\n";
  system("pause");
  regra=le_regras(regras,regra);//Chama a função de leitura do aquivo regra.txt
  palavra=le_palavras(palavras, palavra);//Chama a função de leitura do aquivo palavra.txt
  do{
      op=menu(regras, regra, palavras, palavra);
      if (op == 1)
      {
        system("cls");
        do{
            mostra(palavras, palavra, 2);
            cout<< "\tDigite a linha em que dejesa verificar a linguagem\n\t";
            cin>> line;
            line--;
            if(line < 0 || line >= palavra)
            {
              system("cls");
              cout<< "\n\n\n\t\tLinha invalida\n\n\n";
              system("pause");
            }
        }while(line < 0 || line >= palavra);
        result=check_line(regras, regra, palavras, palavra, line);
        if(result == true)
        {
            cout<< "\n\n\tA palavra e valida \n";
            cout<< "\n\t" << palavras[line] << "\n\n";
        }
        else
        {
            cout<< "\n\n\tA palavra e invalida \n";
            cout<< "\n\t" <<palavras[line] << "\n\n";
        }
        system("pause");
      }
      else
        if(op == 2)
        {
            system("cls");
         for(line=0; line<palavra; line++)
         {
            result=check_line(regras, regra, palavras, palavra, line);
            if(result == true)
            {
               cout<< "\n\n\tA palavra e valida \n";
               cout<< "\n\t" << palavras[line] << "\n\n";
            }
            else
            {
               cout<< "\n\n\tA palavra e invalida \n";
               cout<< "\n\t" <<palavras[line] << "\n\n";
            }
            
         }
         system("pause");
      }
  }while(op != 3);
}

int le_regras(char regras[lin][col], int regra)
{
  char getchar[col];

  ifstream inregra("C:\\LFA\\regra.txt", ios::in);// Função de abertura de arquivo

  if( !inregra )// Verifica se o arquivo foi aberto com sucesso
  {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de regra.txt\n\n";
      exit(1);
  }

  while(inregra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
  {
      strcpy_s(regras[regra], getchar);//Copia o valor do vetor getchar para a linha da matriz regras no indice regra.
      regra++;// passa para o proximo indice
  }
  return regra;//retorna a ultima linha (indice da linha) livre da matriz regras
}

int le_palavras(char palavras[lin][col], int palavra)
{
  char getchar[col];

  ifstream inpalavra("C:\\LFA\\palavra.txt", ios::in);// Função de abertura de arquivo

  if( !inpalavra )// Verifica se o arquivo foi aberto com sucesso
  {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de palavra.txt\n\n";
      exit(1);
  }

  while(inpalavra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
  {
      strcpy_s(palavras[palavra], getchar);//Copia o valor do vetor getchar para a linha da matriz palavras no indice palavra.
      palavra++;// passa para o proximo indice
  }
  return palavra;//retorna a ultima linha (indice da linha) livre da matriz palavras
}

void mostra(char matriz[lin][col], int marcador_de_fim, int indicador)
{
  int l;

  cout<< "\t\t=======================================\n" << "\t\t\t\t";
  if(indicador == 1)
      cout<< "Regras";
  else
      cout<< "Palavras";
  cout<<"\n" << "\t\t=======================================\n" ;
  for(l=0; l<marcador_de_fim; l++)//Percorre todos os indices de linha da matriz, até antes do seu ultimo indice de linha vazio
  {
    if(indicador != 1)
        cout<< "\t\tLinha " << l+1 << " | "<< matriz[l] << endl;
    else
        cout<< "\t\t" << matriz[l] << endl;
  }
  cout<< "\n\n";
}

/*void calc_sizechar(char matriz[lin][col], int marcador_de_fim)
{
  int l, size;

  for(l=0; l<marcador_de_fim; l++)
  {
      size=strlen(matriz[l]);
      cout<< "A linha " << l+1 << " possui " << size << " caracteres\n";
  }
}*/

int menu(char regras[lin][col],int regra, char palavras[lin][col], int palavra)
{
  int op;

  do{
  system("cls");
  mostra(regras,regra, 1);
  mostra(palavras, palavra, 2);
  cout<< "\t\t=======================================\n" << "\t\t\t\tMenu\n" << "\t\t=======================================\n";
  cout<< "\t\t1- Escolhe qual linha sera testada\n";
  cout<< "\t\t2- Todas as linguagem seram testadas\n";
  cout<< "\t\t3- Sair\n";
  cout<< "\t\t=======================================\n";
  cout<< "\n\t\tDigite a opcao desejada\n\t\t";
  cin>> op;
  if(op < 1 || op > 3)
  {
      system("cls");
      cout<< "\n\n\n\t\tOpcao invalida\n\n\n";
      system("pause");
  }
  }while(op < 1 || op > 3);
  return op;
}

dynamic *start()//Inicializa um vetor dinamico
{
  return NULL;
}

dynamic *request_new(dynamic *vet)//Requere um novo espaço de memória para a pilha
{
  dynamic *novo;

  novo=(dynamic*) malloc (sizeof(dynamic));
  novo->prox=vet;
  return novo;
}

dynamic *remove(dynamic *vet)//Desempliha o valor do topo da pilha
{
  dynamic *ant=vet;

  if(vet != NULL)
      vet=vet->prox;
  else
      return NULL;
 
  free(ant);
  return vet;
}

int getline_state(char regras[lin][col],int regra, int state)//Procura a linha da regra correspondente ao estado
{
  int l=5;

  while(l < regra && atoi(&regras[l][2]) != state)
  {
    if(regras[l][4] == '?' && regras[l][6] == '?')
        return l;
      l++;
  }
  return l;
}

bool check_line(char regras[lin][col],int regra, char palavras[lin][col], int palavra, int line)//Checa a palavra de uma linha, conforme a regra para determinar se é verdadeiro ou falso
{
  dynamic *pilha;
  int cont, c, state, stateline, flag=0;

  state=atoi(&regras[3][1]);//Estado recebe o valor inicial convertido em inteiro
  if(state < 0)//Valida se o estado é valido >= 0
  {
      cout<< "\n\n\tValor invalido para o estado o estado deve ser maior ou igua a zero\n\n";
      system("pause");
      exit(1);//Fecha a função relatando um erro, valor invalido para o estado;
  }

  pilha=start();//Inicia a pilha

  cont=strlen(palavras[line]);//Conta quantos caracteres a palavra tem
  for(c=0; c<cont; c++)
  {
      stateline = getline_state(regras, regra, state);//Pega a regra apontada pelo estado
      do{
        flag=0;//Valida se a regra para o caractere foi encontrada, 0= não encontrado
      if(state == atoi(&regras[stateline][2]) && palavras[line][c] == regras[stateline][4] && (regras[stateline][6] == '?'|| valida(pilha, regras[stateline][6])))//Compara a a letra com a regra
        {
            flag=1;//Valida se a regra para o caractere foi encontrada, 1= encontrado
            if(pilha == NULL)//Valida se a pilha esta vasia
            {           
              state=atoi(&regras[stateline][12]);//Recebe o novo estado
              if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
              {
                  pilha=request_new(pilha);//Requisita um novo espaço de memória
                  pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
              }
              else
              {
                  system("cls");
                  cout<< "\n\nO valor inicial não pode conter '-' vazio, regra invalida\n\n";
                  system("pause");
                  exit(1);
              }
            }
            else//Se não é o primeiro caracter então
                if(regras[stateline][6] == pilha->info)//Checa se realmente a regra é valida com o valor q é lido da pilha en relação ao da regra.
              {
                  state=atoi(&regras[stateline][12]);//Recebe o novo estado
                  if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
                  {
                    pilha=request_new(pilha);//Requisita um novo espaço de memória
                    pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
                  }
                  else//Se o valor é "-" remove um valor da pilha
                    pilha=remove(pilha);
              }
        }
        else//Se não encontrar o caracter correspondente vai para a proxima linha da regra pra tentar encontrar
            stateline++;
     

      }while(stateline < regra && (atoi(&regras[4][1]) != state && flag != 1));//Garante que enquanto percorre as linha do vertor regras e no campo estado é igual ao ultimo estado, caso não seja o valor é a palavra é invalida, ou se caracter não foi encontrado continua até ser ou se o esto for diferente.
      /*if(atoi(&regras[stateline][2]) == state)//Garante que não há regra para a letra na palavra, que para o estado é invalido este caractere, ou seja não há regra escrita para este caractere neste estado, a palavra é invalida.
        return true;*/
  }

  if(c==cont && pilha == NULL)//Se a pilha esta vazia e a fita acabou
  {
    state=atoi(&regras[4][1]);//Recebe o estado final
    stateline = getline_state(regras, regra, state);//Pega a regra apontada pelo estado
    if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
    {
        pilha=request_new(pilha);//Requisita um novo espaço de memória
        pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
    }
    else//Se o valor é "-" remove um valor da pilha
        pilha=remove(pilha);

    if(state == atoi(&regras[4][1]))
        return true;
  }
  else
    return false;

  /*if(pilha == NULL && state == atoi(&regras[4][1]))//Valida se a pilha esta vazia e se o estado é igual o estado final, se sim é verdadeiro
  {
      return true;
  }
  else//Se não é falso*/
}

bool valida(dynamic *pilha, char val)//Evita que ocorra o erro de comparação com um endereço nulo
{
   if(pilha == NULL)
      return false;
   else
      if(pilha->info == val)
         return true;

   return false;
}

regra.txt

Código:

q0,q1,q2
a,b
X
q0
q2
(q0,a,?):=(q1,X)
(q1,a,X):=(q1,X)
(q1,b,X):=(q1,-)
(q1,b,?):=(q1,X)
(q1,?,?):=(q2,-)

palavra.txt

Código:

ab
aabb
abb

ab = Valido
aabb = Valido
abb = Invalido

Código:

#include <iostream>
#include <fstream>//Bilioteca para leitura e escrita de arquivos
#include <string>
#include <stdlib.h>
using namespace std;
using std::ifstream;//Função de abertura de arquivo;

const int lin=100, col=100;

struct dynamic_vet
        {
            char info;
            dynamic_vet *prox;
        };

typedef struct dynamic_vet dynamic;

int le_regras(char regras[lin][col], int regra);//Le o arquivo regra.txt
int le_palavras(char palavras[lin][col], int palavra);//Le o arquivo palavra.txt
void mostra(char matriz[lin][col], int marcador_de_fim, int indicador);//Mostra toda a matriz que possui dados
//void calc_sizechar(char matriz[lin][col], int marcador_de_fim);//Conta quantos caracteres tem em cada linha
int menu(char regras[lin][col],int regra, char palavras[lin][col], int palavra);
dynamic *start();//Inicializa um vetor dinamico
dynamic *request_new(dynamic *vet);
dynamic *remove(dynamic *vet);
int getline_state(char regras[lin][col],int regra, int state);
bool check_line(char regras[lin][col],int regra, char palavras[lin][col], int palavra, int line);//Compara a liguagem da linha escolhida, seguindo as regras, e retorna verdadeiro ou falso
bool valida(dynamic *pilha, char val);

void main()
{
  char regras[lin][col], palavras[lin][col];
  int regra=0, palavra=0, op, line;
  bool result;

  cout<< "Os arquivos devem estar na pasta C:>LFA>regra.txt\ne C:>LFA>palavra.txt, e nao devem ter mais que "<< lin << " Linhas \n\n" << "Os aquivos ja estao na pasata solicitada?\ne tambem com os nome solicitados?\n\n";
  system("pause");
  regra=le_regras(regras,regra);//Chama a função de leitura do aquivo regra.txt
  palavra=le_palavras(palavras, palavra);//Chama a função de leitura do aquivo palavra.txt
  do{
      op=menu(regras, regra, palavras, palavra);
      if (op == 1)
      {
        system("cls");
        do{
            mostra(palavras, palavra, 2);
            cout<< "\tDigite a linha em que dejesa verificar a linguagem\n\t";
            cin>> line;
            line--;
            if(line < 0 || line >= palavra)
            {
              system("cls");
              cout<< "\n\n\n\t\tLinha invalida\n\n\n";
              system("pause");
            }
        }while(line < 0 || line >= palavra);
        result=check_line(regras, regra, palavras, palavra, line);
        if(result == true)
        {
            cout<< "\n\n\tA palavra e valida \n";
            cout<< "\n\t" << palavras[line] << "\n\n";
        }
        else
        {
            cout<< "\n\n\tA palavra e invalida \n";
            cout<< "\n\t" <<palavras[line] << "\n\n";
        }
        system("pause");
      }
      else
        if(op == 2)
        {
            system("cls");
         for(line=0; line<palavra; line++)
         {
            result=check_line(regras, regra, palavras, palavra, line);
            if(result == true)
            {
               cout<< "\n\n\tA palavra e valida \n";
               cout<< "\n\t" << palavras[line] << "\n\n";
            }
            else
            {
               cout<< "\n\n\tA palavra e invalida \n";
               cout<< "\n\t" <<palavras[line] << "\n\n";
            }
            
         }
         system("pause");
      }
  }while(op != 3);
}

int le_regras(char regras[lin][col], int regra)
{
  char getchar[col];

  ifstream inregra("C:\\LFA\\regra.txt", ios::in);// Função de abertura de arquivo

  if( !inregra )// Verifica se o arquivo foi aberto com sucesso
  {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de regra.txt\n\n";
      exit(1);
  }

  while(inregra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
  {
      strcpy_s(regras[regra], getchar);//Copia o valor do vetor getchar para a linha da matriz regras no indice regra.
      regra++;// passa para o proximo indice
  }
  return regra;//retorna a ultima linha (indice da linha) livre da matriz regras
}

int le_palavras(char palavras[lin][col], int palavra)
{
  char getchar[col];

  ifstream inpalavra("C:\\LFA\\palavra.txt", ios::in);// Função de abertura de arquivo

  if( !inpalavra )// Verifica se o arquivo foi aberto com sucesso
  {
      cout<< "O arquivo nao pode ser aberto\n por que nao foi encontrado ou esta com o nome diferente de palavra.txt\n\n";
      exit(1);
  }

  while(inpalavra.getline(getchar, col))// Copia linha por linha do arquivo para o vetor do tipo char getchar
  {
      strcpy_s(palavras[palavra], getchar);//Copia o valor do vetor getchar para a linha da matriz palavras no indice palavra.
      palavra++;// passa para o proximo indice
  }
  return palavra;//retorna a ultima linha (indice da linha) livre da matriz palavras
}

void mostra(char matriz[lin][col], int marcador_de_fim, int indicador)
{
  int l;

  cout<< "\t\t=======================================\n" << "\t\t\t\t";
  if(indicador == 1)
      cout<< "Regras";
  else
      cout<< "Palavras";
  cout<<"\n" << "\t\t=======================================\n" ;
  for(l=0; l<marcador_de_fim; l++)//Percorre todos os indices de linha da matriz, até antes do seu ultimo indice de linha vazio
  {
    if(indicador != 1)
        cout<< "\t\tLinha " << l+1 << " | "<< matriz[l] << endl;
    else
        cout<< "\t\t" << matriz[l] << endl;
  }
  cout<< "\n\n";
}

/*void calc_sizechar(char matriz[lin][col], int marcador_de_fim)
{
  int l, size;

  for(l=0; l<marcador_de_fim; l++)
  {
      size=strlen(matriz[l]);
      cout<< "A linha " << l+1 << " possui " << size << " caracteres\n";
  }
}*/

int menu(char regras[lin][col],int regra, char palavras[lin][col], int palavra)
{
  int op;

  do{
  system("cls");
  mostra(regras,regra, 1);
  mostra(palavras, palavra, 2);
  cout<< "\t\t=======================================\n" << "\t\t\t\tMenu\n" << "\t\t=======================================\n";
  cout<< "\t\t1- Escolhe qual linha sera testada\n";
  cout<< "\t\t2- Todas as linguagem seram testadas\n";
  cout<< "\t\t3- Sair\n";
  cout<< "\t\t=======================================\n";
  cout<< "\n\t\tDigite a opcao desejada\n\t\t";
  cin>> op;
  if(op < 1 || op > 3)
  {
      system("cls");
      cout<< "\n\n\n\t\tOpcao invalida\n\n\n";
      system("pause");
  }
  }while(op < 1 || op > 3);
  return op;
}

dynamic *start()//Inicializa um vetor dinamico
{
  return NULL;
}

dynamic *request_new(dynamic *vet)//Requere um novo espaço de memória para a pilha
{
  dynamic *novo;

  novo=(dynamic*) malloc (sizeof(dynamic));
  novo->prox=vet;
  return novo;
}

dynamic *remove(dynamic *vet)//Desempliha o valor do topo da pilha
{
  dynamic *ant=vet;

  if(vet != NULL)
      vet=vet->prox;
  else
      return NULL;
 
  free(ant);
  return vet;
}

int getline_state(char regras[lin][col],int regra, int state)//Procura a linha da regra correspondente ao estado
{
  int l=5;

  while(l < regra && atoi(&regras[l][2]) != state)
  {
    if(regras[l][4] == '?' && regras[l][6] == '?')
        return l;
      l++;
  }
  return l;
}

bool check_line(char regras[lin][col],int regra, char palavras[lin][col], int palavra, int line)//Checa a palavra de uma linha, conforme a regra para determinar se é verdadeiro ou falso
{
  dynamic *pilha;
  int cont, c, state, stateline, flag=0;

  state=atoi(&regras[3][1]);//Estado recebe o valor inicial convertido em inteiro
  if(state < 0)//Valida se o estado é valido >= 0
  {
      cout<< "\n\n\tValor invalido para o estado o estado deve ser maior ou igua a zero\n\n";
      system("pause");
      exit(1);//Fecha a função relatando um erro, valor invalido para o estado;
  }

  pilha=start();//Inicia a pilha

  cont=strlen(palavras[line]);//Conta quantos caracteres a palavra tem
  for(c=0; c<cont; c++)
  {
      stateline = getline_state(regras, regra, state);//Pega a regra apontada pelo estado
      do{
        flag=0;//Valida se a regra para o caractere foi encontrada, 0= não encontrado
      if(state == atoi(&regras[stateline][2]) && palavras[line][c] == regras[stateline][4] && (regras[stateline][6] == '?'|| valida(pilha, regras[stateline][6])))//Compara a a letra com a regra
        {
            flag=1;//Valida se a regra para o caractere foi encontrada, 1= encontrado
            if(pilha == NULL)//Valida se a pilha esta vasia
            {           
              state=atoi(&regras[stateline][12]);//Recebe o novo estado
              if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
              {
                  pilha=request_new(pilha);//Requisita um novo espaço de memória
                  pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
              }
              else
              {
                  system("cls");
                  cout<< "\n\nO valor inicial não pode conter '-' vazio, regra invalida\n\n";
                  system("pause");
                  exit(1);
              }
            }
            else//Se não é o primeiro caracter então
                if(regras[stateline][6] == pilha->info)//Checa se realmente a regra é valida com o valor q é lido da pilha en relação ao da regra.
              {
                  state=atoi(&regras[stateline][12]);//Recebe o novo estado
                  if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
                  {
                    pilha=request_new(pilha);//Requisita um novo espaço de memória
                    pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
                  }
                  else//Se o valor é "-" remove um valor da pilha
                    pilha=remove(pilha);
              }
        }
        else//Se não encontrar o caracter correspondente vai para a proxima linha da regra pra tentar encontrar
            stateline++;
     

      }while(stateline < regra && (atoi(&regras[4][1]) != state && flag != 1));//Garante que enquanto percorre as linha do vertor regras e no campo estado é igual ao ultimo estado, caso não seja o valor é a palavra é invalida, ou se caracter não foi encontrado continua até ser ou se o esto for diferente.
      /*if(atoi(&regras[stateline][2]) == state)//Garante que não há regra para a letra na palavra, que para o estado é invalido este caractere, ou seja não há regra escrita para este caractere neste estado, a palavra é invalida.
        return true;*/
  }

  if(c==cont && pilha == NULL)//Se a pilha esta vazia e a fita acabou
  {
    state=atoi(&regras[4][1]);//Recebe o estado final
    stateline = getline_state(regras, regra, state);//Pega a regra apontada pelo estado
    if(regras[stateline][14] != '-')//Checa o valor que será colocado ou retirado da pilha, este simbolo "-" remove da prilha
    {
        pilha=request_new(pilha);//Requisita um novo espaço de memória
        pilha->info=regras[stateline][14];//Pega o caracter correnpondente da regra e adiciona a pilha
    }
    else//Se o valor é "-" remove um valor da pilha
        pilha=remove(pilha);

    if(state == atoi(&regras[4][1]))
        return true;
  }
  else
    return false;

  /*if(pilha == NULL && state == atoi(&regras[4][1]))//Valida se a pilha esta vazia e se o estado é igual o estado final, se sim é verdadeiro
  {
      return true;
  }
  else//Se não é falso*/
}

bool valida(dynamic *pilha, char val)//Evita que ocorra o erro de comparação com um endereço nulo
{
   if(pilha == NULL)
      return false;
   else
      if(pilha->info == val)
         return true;

   return false;
}