Tutoriais - Linguagens Formais e Autômatos
Tutoriais
Linguagens Formais e Autômatos

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.lfa.tutorial02.exercicio235;

import java.util.HashMap;
import java.util.Map;

/**
 * Estado do Automato Finito Deterministico
 */
public class State
{
  /**
   * Estado eh de aceitacao
   */
  private boolean accept;

  /**
   * Transicao de estados
   */
  private Map<Character, Integer> transitions;

  /**
   * Constructor
   *
   * @param accept estado eh de aceitacao
   */
  public State(boolean accept)
  {
    this.accept = accept;

    transitions = new HashMap<>();
  }

  /**
   * Retornar se o estado eh de aceitacao
   *
   * @return true se o estado eh de aceitacao,
   *   false em caso contrario
   */
  public boolean isAccept()
  {
    return accept;
  }

  /**
   * Adicionar uma transicao de estado
   *
   * @param symbol simbolo corrente
   * @param state novo estado
   */
  public void addTransition(Character symbol, Integer state)
  {
    transitions.put(symbol, state);
  }

  /**
   * Retornar o novo estado
   *
   * @param symbol simbolo corrente
   * @return novo estado
   */
  public Integer getTransition(Character symbol)
  {
    return transitions.get(symbol);
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.lfa.tutorial02.exercicio235;

import java.util.HashMap;
import java.util.Map;

/**
 * Automato Finito Deterministico (AFD)
 */
public class DeterministicFiniteAutomaton
{
  /**
   * Estados do Automato Finito Deterministico (AFD)
   */
  private Map<Integer, State> states;

  /**
   * Constructor
   */
  public DeterministicFiniteAutomaton()
  {
    states = new HashMap<>();

    State q0 = new State(false);
    q0.addTransition('a', 1);
    q0.addTransition('b', 4);
    q0.addTransition('d', 7);
    states.put(0, q0);

    State q1 = new State(false);
    q1.addTransition('b', 2);
    states.put(1, q1);

    State q2 = new State(false);
    q2.addTransition('c', 3);
    states.put(2, q2);

    State q3 = new State(false);
    q3.addTransition('d', 10);
    states.put(3, q3);

    State q4 = new State(false);
    q4.addTransition('a', 5);
    states.put(4, q4);

    State q5 = new State(false);
    q5.addTransition('b', 6);
    states.put(5, q5);

    State q6 = new State(false);
    q6.addTransition('a', 16);
    states.put(6, q6);

    State q7 = new State(false);
    q7.addTransition('c', 8);
    states.put(7, q7);

    State q8 = new State(false);
    q8.addTransition('b', 9);
    states.put(8, q8);

    State q9 = new State(false);
    q9.addTransition('a', 16);
    states.put(9, q9);

    State q10 = new State(false);
    q10.addTransition('a', 11);
    q10.addTransition('b', 15);
    q10.addTransition('c', 19);
    q10.addTransition('d', 10);
    states.put(10, q10);

    State q11 = new State(false);
    q11.addTransition('a', 11);
    q11.addTransition('b', 12);
    q11.addTransition('c', 19);
    q11.addTransition('d', 10);
    states.put(11, q11);

    State q12 = new State(false);
    q12.addTransition('a', 16);
    q12.addTransition('b', 15);
    q12.addTransition('c', 13);
    q12.addTransition('d', 10);
    states.put(12, q12);

    State q13 = new State(false);
    q13.addTransition('a', 11);
    q13.addTransition('b', 14);
    q13.addTransition('c', 20);
    q13.addTransition('d', 10);
    states.put(13, q13);

    State q14 = new State(false);
    q14.addTransition('a', 16);
    q14.addTransition('b', 15);
    q14.addTransition('c', 25);
    q14.addTransition('d', 10);
    states.put(14, q14);

    State q15 = new State(false);
    q15.addTransition('a', 16);
    q15.addTransition('b', 15);
    q15.addTransition('c', 19);
    q15.addTransition('d', 10);
    states.put(15, q15);

    State q16 = new State(false);
    q16.addTransition('a', 11);
    q16.addTransition('b', 12);
    q16.addTransition('c', 19);
    q16.addTransition('d', 17);
    states.put(16, q16);

    State q17 = new State(false);
    q17.addTransition('a', 11);
    q17.addTransition('b', 15);
    q17.addTransition('c', 18);
    q17.addTransition('d', 10);
    states.put(17, q17);

    State q18 = new State(false);
    q18.addTransition('a', 11);
    q18.addTransition('b', 15);
    q18.addTransition('c', 20);
    q18.addTransition('d', 29);
    states.put(18, q18);

    State q19 = new State(false);
    q19.addTransition('a', 11);
    q19.addTransition('b', 15);
    q19.addTransition('c', 20);
    q19.addTransition('d', 10);
    states.put(19, q19);

    State q20 = new State(false);
    q20.addTransition('a', 11);
    q20.addTransition('b', 15);
    q20.addTransition('c', 20);
    q20.addTransition('d', 21);
    states.put(20, q20);

    State q21 = new State(false);
    q21.addTransition('a', 22);
    q21.addTransition('b', 15);
    q21.addTransition('c', 19);
    q21.addTransition('d', 10);
    states.put(21, q21);

    State q22 = new State(false);
    q22.addTransition('a', 11);
    q22.addTransition('b', 34);
    q22.addTransition('c', 19);
    q22.addTransition('d', 10);
    states.put(22, q22);

    State q23 = new State(false);
    q23.addTransition('a', 23);
    q23.addTransition('b', 24);
    q23.addTransition('c', 28);
    q23.addTransition('d', 32);
    states.put(23, q23);

    State q24 = new State(false);
    q24.addTransition('a', 23);
    q24.addTransition('b', 24);
    q24.addTransition('c', 25);
    q24.addTransition('d', 32);
    states.put(24, q24);

    State q25 = new State(false);
    q25.addTransition('a', 23);
    q25.addTransition('b', 24);
    q25.addTransition('c', 26);
    q25.addTransition('d', 29);
    states.put(25, q25);

    State q26 = new State(false);
    q26.addTransition('a', 27);
    q26.addTransition('b', 24);
    q26.addTransition('c', 28);
    q26.addTransition('d', 29);
    states.put(26, q26);

    State q27 = new State(true);
    q27.addTransition('a', 23);
    q27.addTransition('b', 24);
    q27.addTransition('c', 28);
    q27.addTransition('d', 32);
    q27.addTransition('$', 27);
    states.put(27, q27);

    State q28 = new State(false);
    q28.addTransition('a', 23);
    q28.addTransition('b', 24);
    q28.addTransition('c', 28);
    q28.addTransition('d', 29);
    states.put(28, q28);

    State q29 = new State(false);
    q29.addTransition('a', 30);
    q29.addTransition('b', 24);
    q29.addTransition('c', 28);
    q29.addTransition('d', 32);
    states.put(29, q29);

    State q30 = new State(false);
    q30.addTransition('a', 23);
    q30.addTransition('b', 24);
    q30.addTransition('c', 31);
    q30.addTransition('d', 32);
    states.put(30, q30);

    State q31 = new State(true);
    q31.addTransition('a', 23);
    q31.addTransition('b', 24);
    q31.addTransition('c', 28);
    q31.addTransition('d', 29);
    q31.addTransition('$', 31);
    states.put(31, q31);

    State q32 = new State(false);
    q32.addTransition('a', 33);
    q32.addTransition('b', 24);
    q32.addTransition('c', 28);
    q32.addTransition('d', 32);
    states.put(32, q32);

    State q33 = new State(false);
    q33.addTransition('a', 23);
    q33.addTransition('b', 34);
    q33.addTransition('c', 28);
    q33.addTransition('d', 32);
    states.put(33, q33);

    State q34 = new State(false);
    q34.addTransition('a', 23);
    q34.addTransition('b', 24);
    q34.addTransition('c', 35);
    q34.addTransition('d', 32);
    states.put(34, q34);

    State q35 = new State(true);
    q35.addTransition('a', 23);
    q35.addTransition('b', 24);
    q35.addTransition('c', 26);
    q35.addTransition('d', 29);
    q35.addTransition('$', 35);
    states.put(35, q35);
  }

  /**
   * Formatar o estado para impressao
   *
   * @param state estado
   * @return estado formatado para impressao
   */
  private String formatState(Integer state)
  {
    if((states.size() < 100) && (state < 10))
    {
      return "\nq" + state + "  - ";
    }

    return "\nq" + state + " - ";
  }

  /**
   * Reconhecer a sentenca de entrada
   *
   * @param sentence sentenca de entrada
   * @return true caso a sentenca de entrada pertenca a linguagem,
   *   false em caso contrario
   */
  public boolean recognize(String sentence)
  {
    String input = sentence + "$";

    System.out.print("Observação: \"$\" representa o fim da sentença");

    Integer state = 0;

    int length = input.length();

    for(int symbol = 0; symbol < length; symbol++)
    {
      System.out.print(formatState(state));

      for(int index = 0; index < length; index++)
      {
        if(index != symbol)
        {
          System.out.print(" " + input.charAt(index) + " ");
        }
        else
        {
          System.out.print("[" + input.charAt(index) + "]");
        }
      }

      state = states.get(state).getTransition(input.charAt(symbol));

      if(state == null)
      {
        System.out.println(" - REJEITA");

        return false;
      }
    }

    if(states.get(state).isAccept())
    {
      System.out.println(" - ACEITA");
    }
    else
    {
      System.out.println(" - REJEITA");
    }

    return states.get(state).isAccept();
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.lfa.tutorial02.exercicio235;

import java.util.Scanner;

/**
 * Testar o Automato Finito Deterministico (AFD)
 */
public class Application
{
  /**
   * Constructor
   */
  private Application()
  {

  }

  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    Scanner scanner = new Scanner(System.in);

    System.out.print("Analise a sentença: ");
    String sentence = scanner.nextLine().trim();

    scanner.close();

    if(sentence.indexOf("$") >= 0)
    {
      System.out.println("A sentença \"" + sentence + "\" é inválida");

      return;
    }

    DeterministicFiniteAutomaton afd = new DeterministicFiniteAutomaton();

    afd.recognize(sentence);
  }
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#ifndef STATE_HPP_
#define STATE_HPP_

#include <map>

/**
 * Estado do Automato Finito Deterministico
 */
class State
{
  public:

  /**
   * Constructor
   *
   * @param accept estado eh de aceitacao
   */
  State(const bool accept);

  /**
   * Destructor
   */
  virtual ~State();

  /**
   * Retornar se o estado eh de aceitacao
   *
   * @return true (1) se o estado eh de aceitacao,
   *   false (0) em caso contrario
   */
  bool isAccept() const;

  /**
   * Adicionar uma transicao de estado
   *
   * @param symbol simbolo corrente
   * @param state novo estado
   */
  void addTransition(char symbol, int state);

  /**
   * Retornar o novo estado
   *
   * @param symbol simbolo corrente
   * @return novo estado
   */
  int getTransition(char symbol) const;

  private:

  /**
   * Estado eh de aceitacao
   */
  bool accept;

  /**
   * Transicao de estados
   */
  std::map<char, int>* transitions;
};

#endif

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <map>

#include "State.hpp"

/**
 * Constructor
 *
 * @param accept estado eh de aceitacao
 */
State::State(const bool accept)
{
  State::accept = accept;

  transitions = new std::map<char, int>();
}

/**
 * Destructor
 */
State::~State()
{
  transitions->clear();

  delete transitions;
}

/**
 * Retornar se o estado eh de aceitacao
 *
 * @return true (1) se o estado eh de aceitacao,
 *   false (0) em caso contrario
 */
bool State::isAccept() const
{
  return accept;
}

/**
 * Adicionar uma transicao de estado
 *
 * @param symbol simbolo corrente
 * @param state novo estado
 */
void State::addTransition(char symbol, int state)
{
  transitions->insert(std::pair<char, int>(symbol, state));
}

/**
 * Retornar o novo estado
 *
 * @param symbol simbolo corrente
 * @return novo estado
 */
int State::getTransition(char symbol) const
{
  if(transitions->find(symbol) != transitions->end())
  {
    return transitions->find(symbol)->second;
  }

  return -1;
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#ifndef DETERMINISTIC_FINITE_AUTOMATON_HPP_
#define DETERMINISTIC_FINITE_AUTOMATON_HPP_

#include <map>
#include <string>

#include "State.hpp"

/**
 * Automato Finito Deterministico (AFD)
 */
class DeterministicFiniteAutomaton
{
  public:

  /**
   * Constructor
   */
  DeterministicFiniteAutomaton();

  /**
   * Destructor
   */
  virtual ~DeterministicFiniteAutomaton();

  /**
   * Reconhecer a sentenca de entrada
   *
   * @param sentence sentenca de entrada
   * @return true (1) caso a sentenca de entrada pertenca a linguagem,
   *   false (0) em caso contrario
   */
  bool recognize(std::string sentence);

  private:

  /**
   * Estados do Automato Finito Deterministico (AFD)
   */
  std::map<int, State*>* states;

  /**
   * Formatar o estado para impressao
   *
   * @param state estado
   * @return estado formatado para impressao
   */
  std::string formatState(int state);
};

#endif

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <iostream>
#include <map>
#include <sstream>
#include <string>

#include "DeterministicFiniteAutomaton.hpp"

/**
 * Constructor
 */
DeterministicFiniteAutomaton::DeterministicFiniteAutomaton()
{
  states = new std::map<int, State*>();

  State* q0 = new State(false);
  q0->addTransition('a', 1);
  q0->addTransition('b', 4);
  q0->addTransition('d', 7);
  states->insert(std::pair<int, State*>(0, q0));

  State* q1 = new State(false);
  q1->addTransition('b', 2);
  states->insert(std::pair<int, State*>(1, q1));

  State* q2 = new State(false);
  q2->addTransition('c', 3);
  states->insert(std::pair<int, State*>(2, q2));

  State* q3 = new State(false);
  q3->addTransition('d', 10);
  states->insert(std::pair<int, State*>(3, q3));

  State* q4 = new State(false);
  q4->addTransition('a', 5);
  states->insert(std::pair<int, State*>(4, q4));

  State* q5 = new State(false);
  q5->addTransition('b', 6);
  states->insert(std::pair<int, State*>(5, q5));

  State* q6 = new State(false);
  q6->addTransition('a', 16);
  states->insert(std::pair<int, State*>(6, q6));

  State* q7 = new State(false);
  q7->addTransition('c', 8);
  states->insert(std::pair<int, State*>(7, q7));

  State* q8 = new State(false);
  q8->addTransition('b', 9);
  states->insert(std::pair<int, State*>(8, q8));

  State* q9 = new State(false);
  q9->addTransition('a', 16);
  states->insert(std::pair<int, State*>(9, q9));

  State* q10 = new State(false);
  q10->addTransition('a', 11);
  q10->addTransition('b', 15);
  q10->addTransition('c', 19);
  q10->addTransition('d', 10);
  states->insert(std::pair<int, State*>(10, q10));

  State* q11 = new State(false);
  q11->addTransition('a', 11);
  q11->addTransition('b', 12);
  q11->addTransition('c', 19);
  q11->addTransition('d', 10);
  states->insert(std::pair<int, State*>(11, q11));

  State* q12 = new State(false);
  q12->addTransition('a', 16);
  q12->addTransition('b', 15);
  q12->addTransition('c', 13);
  q12->addTransition('d', 10);
  states->insert(std::pair<int, State*>(12, q12));

  State* q13 = new State(false);
  q13->addTransition('a', 11);
  q13->addTransition('b', 14);
  q13->addTransition('c', 20);
  q13->addTransition('d', 10);
  states->insert(std::pair<int, State*>(13, q13));

  State* q14 = new State(false);
  q14->addTransition('a', 16);
  q14->addTransition('b', 15);
  q14->addTransition('c', 25);
  q14->addTransition('d', 10);
  states->insert(std::pair<int, State*>(14, q14));

  State* q15 = new State(false);
  q15->addTransition('a', 16);
  q15->addTransition('b', 15);
  q15->addTransition('c', 19);
  q15->addTransition('d', 10);
  states->insert(std::pair<int, State*>(15, q15));

  State* q16 = new State(false);
  q16->addTransition('a', 11);
  q16->addTransition('b', 12);
  q16->addTransition('c', 19);
  q16->addTransition('d', 17);
  states->insert(std::pair<int, State*>(16, q16));

  State* q17 = new State(false);
  q17->addTransition('a', 11);
  q17->addTransition('b', 15);
  q17->addTransition('c', 18);
  q17->addTransition('d', 10);
  states->insert(std::pair<int, State*>(17, q17));

  State* q18 = new State(false);
  q18->addTransition('a', 11);
  q18->addTransition('b', 15);
  q18->addTransition('c', 20);
  q18->addTransition('d', 29);
  states->insert(std::pair<int, State*>(18, q18));

  State* q19 = new State(false);
  q19->addTransition('a', 11);
  q19->addTransition('b', 15);
  q19->addTransition('c', 20);
  q19->addTransition('d', 10);
  states->insert(std::pair<int, State*>(19, q19));

  State* q20 = new State(false);
  q20->addTransition('a', 11);
  q20->addTransition('b', 15);
  q20->addTransition('c', 20);
  q20->addTransition('d', 21);
  states->insert(std::pair<int, State*>(20, q20));

  State* q21 = new State(false);
  q21->addTransition('a', 22);
  q21->addTransition('b', 15);
  q21->addTransition('c', 19);
  q21->addTransition('d', 10);
  states->insert(std::pair<int, State*>(21, q21));

  State* q22 = new State(false);
  q22->addTransition('a', 11);
  q22->addTransition('b', 34);
  q22->addTransition('c', 19);
  q22->addTransition('d', 10);
  states->insert(std::pair<int, State*>(22, q22));

  State* q23 = new State(false);
  q23->addTransition('a', 23);
  q23->addTransition('b', 24);
  q23->addTransition('c', 28);
  q23->addTransition('d', 32);
  states->insert(std::pair<int, State*>(23, q23));

  State* q24 = new State(false);
  q24->addTransition('a', 23);
  q24->addTransition('b', 24);
  q24->addTransition('c', 25);
  q24->addTransition('d', 32);
  states->insert(std::pair<int, State*>(24, q24));

  State* q25 = new State(false);
  q25->addTransition('a', 23);
  q25->addTransition('b', 24);
  q25->addTransition('c', 26);
  q25->addTransition('d', 29);
  states->insert(std::pair<int, State*>(25, q25));

  State* q26 = new State(false);
  q26->addTransition('a', 27);
  q26->addTransition('b', 24);
  q26->addTransition('c', 28);
  q26->addTransition('d', 29);
  states->insert(std::pair<int, State*>(26, q26));

  State* q27 = new State(true);
  q27->addTransition('a', 23);
  q27->addTransition('b', 24);
  q27->addTransition('c', 28);
  q27->addTransition('d', 32);
  q27->addTransition('$', 27);
  states->insert(std::pair<int, State*>(27, q27));

  State* q28 = new State(false);
  q28->addTransition('a', 23);
  q28->addTransition('b', 24);
  q28->addTransition('c', 28);
  q28->addTransition('d', 29);
  states->insert(std::pair<int, State*>(28, q28));

  State* q29 = new State(false);
  q29->addTransition('a', 30);
  q29->addTransition('b', 24);
  q29->addTransition('c', 28);
  q29->addTransition('d', 32);
  states->insert(std::pair<int, State*>(29, q29));

  State* q30 = new State(false);
  q30->addTransition('a', 23);
  q30->addTransition('b', 24);
  q30->addTransition('c', 31);
  q30->addTransition('d', 32);
  states->insert(std::pair<int, State*>(30, q30));

  State* q31 = new State(true);
  q31->addTransition('a', 23);
  q31->addTransition('b', 24);
  q31->addTransition('c', 28);
  q31->addTransition('d', 29);
  q31->addTransition('$', 31);
  states->insert(std::pair<int, State*>(31, q31));

  State* q32 = new State(false);
  q32->addTransition('a', 33);
  q32->addTransition('b', 24);
  q32->addTransition('c', 28);
  q32->addTransition('d', 32);
  states->insert(std::pair<int, State*>(32, q32));

  State* q33 = new State(false);
  q33->addTransition('a', 23);
  q33->addTransition('b', 34);
  q33->addTransition('c', 28);
  q33->addTransition('d', 32);
  states->insert(std::pair<int, State*>(33, q33));

  State* q34 = new State(false);
  q34->addTransition('a', 23);
  q34->addTransition('b', 24);
  q34->addTransition('c', 35);
  q34->addTransition('d', 32);
  states->insert(std::pair<int, State*>(34, q34));

  State* q35 = new State(true);
  q35->addTransition('a', 23);
  q35->addTransition('b', 24);
  q35->addTransition('c', 26);
  q35->addTransition('d', 29);
  q35->addTransition('$', 35);
  states->insert(std::pair<int, State*>(35, q35));
}

/**
 * Destructor
 */
DeterministicFiniteAutomaton::~DeterministicFiniteAutomaton()
{
  while(!states->empty())
  {
    delete states->begin()->second;

    states->erase(states->begin());
  }

  delete states;
}

/**
 * Reconhecer a sentenca de entrada
 *
 * @param sentence sentenca de entrada
 * @return true (1) caso a sentenca de entrada seja reconhecida,
 *   false (0) em caso contrario
 */
bool DeterministicFiniteAutomaton::recognize(std::string sentence)
{
  using namespace std;

  sentence.insert(sentence.end(), '$');

  cout << "Observação: \"$\" representa o fim da sentença";

  int symbol;

  int index;

  int state = 0;

  State* actual;

  int length = sentence.length();

  for(symbol = 0; symbol < length; symbol++)
  {
    cout << formatState(state);

    for(index = 0; index < length; index++)
    {
      if(index != symbol)
      {
        cout << " " << sentence.at(index) << " ";
      }
      else
      {
        cout << "[" << sentence.at(index) << "]";
      }
    }

    actual = states->find(state)->second;

    state = actual->getTransition(sentence.at(symbol));

    if(state == -1)
    {
      cout << " - REJEITA" << endl;

      return false;
    }
  }

  actual = states->find(state)->second;

  if(actual->isAccept())
  {
    cout << " - ACEITA" << endl;
  }
  else
  {
    cout << " - REJEITA" << endl;
  }

  return actual->isAccept();
}

/**
 * Formatar o estado para impressao
 *
 * @param state estado
 * @return estado formatado para impressao
 */
std::string DeterministicFiniteAutomaton::formatState(int state)
{
  using namespace std;

  stringstream buffer;

  buffer << "\nq" << state;

  if((states->size() < 100) && (state < 10))
  {
    buffer << "  - ";
  }
  else
  {
    buffer << " - ";
  }

  return buffer.str();
}

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <iostream>
#include <string>

#include "DeterministicFiniteAutomaton.hpp"

/**
 * Metodo principal da linguagem de programacao C++
 *
 * @param argc quantidade de argumentos na linha de comando (nao utilizado)
 * @param argv argumentos da linha de comando (nao utilizado)
 */
int main(int argc, char** argv)
{
  using namespace std;

  string sentence;

  cout << "Analise a sentença: ";
  cin >> sentence;

  if(sentence.find("$") != string::npos)
  {
    cout << "A sentença \"" << sentence << "\" é inválida" << endl;

    return 1;
  }

  DeterministicFiniteAutomaton* afd = new DeterministicFiniteAutomaton();

  afd->recognize(sentence);

  delete afd;

  return 0;
}

##########################################################################
 # Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  #
 #                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  #
 #                                                                       #
 # Permission is granted to copy, distribute and/or modify this document #
 # under the terms of the GNU Free Documentation License, Version 1.3 or #
 # any later version published by the  Free Software Foundation; with no #
 # Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A #
 # A copy of the  license is included in  the section entitled "GNU Free #
 # Documentation License".                                               #
 #                                                                       #
 # Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             #
 # gcc/g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                       #
 ##########################################################################

g++ -o State.o -c State.cpp

g++ -o DeterministicFiniteAutomaton.o -c DeterministicFiniteAutomaton.cpp

g++ -o Application.o -c Application.cpp

g++ -o application State.o DeterministicFiniteAutomaton.o Application.o

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * gcc (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <stdio.h>
#include <string.h>

/**
 * Definicao das constantes
 */
#define ACEITA  1
#define REJEITA 0

/**
 * Prototipo das funcoes
 */
void console(int, int);
int q0(int);
int q1(int);
int q2(int);
int q3(int);
int q4(int);
int q5(int);
int q6(int);
int q7(int);
int q8(int);
int q9(int);
int q10(int);
int q11(int);
int q12(int);
int q13(int);
int q14(int);
int q15(int);
int q16(int);
int q17(int);
int q18(int);
int q19(int);
int q20(int);
int q21(int);
int q22(int);
int q23(int);
int q24(int);
int q25(int);
int q26(int);
int q27(int);
int q28(int);
int q29(int);
int q30(int);
int q31(int);
int q32(int);
int q33(int);
int q34(int);
int q35(int);

/**
 * Sentenca
 */
char sentence[255];

/**
 * Metodo principal da linguagem de programacao C
 *
 * @param argc quantidade de argumentos na linha de comando (nao utilizado)
 * @param argv argumentos da linha de comando (nao utilizado)
 * @return saida para o sistema operacional (padrao 0)
 */
int main(int argc, char** argv)
{
  printf("Analise a sentença: ");
  fgets(sentence, 255, stdin);

  if(strchr(sentence, '$') != 0)
  {
    sentence[strlen(sentence) - 1] = '\0';
    printf("A sentença \"%s\" é inválida\n", sentence);
    return 1;
  }

  sentence[strlen(sentence) - 1] = '$';

  printf("Observação: \"$\" representa o fim da sentença");

  if(q0(0))
  {
    printf(" - ACEITA\n");
  }
  else
  {
    printf(" - REJEITA\n");
  }

  return 0;
}

/**
 * Imprimir a execucao do automato finito deterministico
 *
 * @param state estado corrente
 * @param symbol simbolo corrente
 */
void console(int state, int symbol)
{
  int i;

  int length = strlen(sentence);

  if(state < 10)
  {
    printf("\nq%i  - ", state);
  }
  else
  {
    printf("\nq%i - ", state);
  }

  for(i = 0; i < length; i++)
  {
    if(i != symbol)
    {
      printf(" %c ", sentence[i]);
    }
    else
    {
      printf("[%c]", sentence[i]);
    }
  }
}

/**
 * Estado q0 (inicial)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q0(int symbol)
{
  console(0, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q1(symbol);
    case 'b': return q4(symbol);
    case 'd': return q7(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q1
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q1(int symbol)
{
  console(1, symbol);

  switch(sentence[symbol++])
  {
    case 'b': return q2(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q2
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q2(int symbol)
{
  console(2, symbol);

  switch(sentence[symbol++])
  {
    case 'c': return q3(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q3
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q3(int symbol)
{
  console(3, symbol);

  switch(sentence[symbol++])
  {
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q4
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q4(int symbol)
{
  console(4, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q5(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q5
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q5(int symbol)
{
  console(5, symbol);

  switch(sentence[symbol++])
  {
    case 'b': return q6(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q6
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q6(int symbol)
{
  console(6, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q16(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q7
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q7(int symbol)
{
  console(7, symbol);

  switch(sentence[symbol++])
  {
    case 'c': return q8(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q8
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q8(int symbol)
{
  console(8, symbol);

  switch(sentence[symbol++])
  {
    case 'b': return q9(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q9
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q9(int symbol)
{
  console(9, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q16(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q10
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q10(int symbol)
{
  console(10, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q15(symbol);
    case 'c': return q19(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q11
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q11(int symbol)
{
  console(11, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q12(symbol);
    case 'c': return q19(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q12
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q12(int symbol)
{
  console(12, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q16(symbol);
    case 'b': return q15(symbol);
    case 'c': return q13(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q13
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q13(int symbol)
{
  console(13, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q14(symbol);
    case 'c': return q20(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q14
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q14(int symbol)
{
  console(14, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q16(symbol);
    case 'b': return q15(symbol);
    case 'c': return q25(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q15
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q15(int symbol)
{
  console(15, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q16(symbol);
    case 'b': return q15(symbol);
    case 'c': return q19(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q16
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q16(int symbol)
{
  console(16, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q12(symbol);
    case 'c': return q19(symbol);
    case 'd': return q17(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q17
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q17(int symbol)
{
  console(17, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q15(symbol);
    case 'c': return q18(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q18
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q18(int symbol)
{
  console(18, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q15(symbol);
    case 'c': return q20(symbol);
    case 'd': return q29(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q19
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q19(int symbol)
{
  console(19, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q15(symbol);
    case 'c': return q20(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q20
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q20(int symbol)
{
  console(20, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q15(symbol);
    case 'c': return q20(symbol);
    case 'd': return q21(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q21
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q21(int symbol)
{
  console(21, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q22(symbol);
    case 'b': return q15(symbol);
    case 'c': return q19(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q22
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q22(int symbol)
{
  console(22, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q11(symbol);
    case 'b': return q34(symbol);
    case 'c': return q19(symbol);
    case 'd': return q10(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q23
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q23(int symbol)
{
  console(23, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q24
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q24(int symbol)
{
  console(24, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q25(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q25
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q25(int symbol)
{
  console(25, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q26(symbol);
    case 'd': return q29(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q26
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q26(int symbol)
{
  console(26, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q27(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q29(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q27 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q27(int symbol)
{
  console(27, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q32(symbol);
    case '$': return ACEITA;
    default : return REJEITA;
  }
}

/**
 * Estado q28
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q28(int symbol)
{
  console(28, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q29(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q29
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q29(int symbol)
{
  console(29, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q30(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q30
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q30(int symbol)
{
  console(30, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q31(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q31 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q31(int symbol)
{
  console(31, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q29(symbol);
    case '$': return ACEITA;
    default : return REJEITA;
  }
}

/**
 * Estado q32
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q32(int symbol)
{
  console(32, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q33(symbol);
    case 'b': return q24(symbol);
    case 'c': return q28(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q33
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q33(int symbol)
{
  console(33, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q34(symbol);
    case 'c': return q28(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q34
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q34(int symbol)
{
  console(34, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q35(symbol);
    case 'd': return q32(symbol);
    default : return REJEITA;
  }
}

/**
 * Estado q35 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 */
int q35(int symbol)
{
  console(35, symbol);

  switch(sentence[symbol++])
  {
    case 'a': return q23(symbol);
    case 'b': return q24(symbol);
    case 'c': return q26(symbol);
    case 'd': return q29(symbol);
    case '$': return ACEITA;
    default : return REJEITA;
  }
}

##########################################################################
 # Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  #
 #                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  #
 #                                                                       #
 # Permission is granted to copy, distribute and/or modify this document #
 # under the terms of the GNU Free Documentation License, Version 1.3 or #
 # any later version published by the  Free Software Foundation; with no #
 # Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A #
 # A copy of the  license is included in  the section entitled "GNU Free #
 # Documentation License".                                               #
 #                                                                       #
 # Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             #
 # gcc/g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                       #
 ##########################################################################

gcc -o DeterministicFiniteAutomaton.o -c DeterministicFiniteAutomaton.c

gcc -o application DeterministicFiniteAutomaton.o

(*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * FreePascal IDE for Linux for x86-64 (version 2.6.2-8)                 *
 *************************************************************************)

program DeterministicFiniteAutomaton;

(**
 * Definicao das constantes
 *)
const
  ACEITA  = true;
  REJEITA = false;

(**
 * Prototipo das funcoes
 *)
procedure console(state : integer; symbol : integer); forward;
function q0(symbol : integer) : boolean; forward;
function q1(symbol : integer) : boolean; forward;
function q2(symbol : integer) : boolean; forward;
function q3(symbol : integer) : boolean; forward;
function q4(symbol : integer) : boolean; forward;
function q5(symbol : integer) : boolean; forward;
function q6(symbol : integer) : boolean; forward;
function q7(symbol : integer) : boolean; forward;
function q8(symbol : integer) : boolean; forward;
function q9(symbol : integer) : boolean; forward;
function q10(symbol : integer) : boolean; forward;
function q11(symbol : integer) : boolean; forward;
function q12(symbol : integer) : boolean; forward;
function q13(symbol : integer) : boolean; forward;
function q14(symbol : integer) : boolean; forward;
function q15(symbol : integer) : boolean; forward;
function q16(symbol : integer) : boolean; forward;
function q17(symbol : integer) : boolean; forward;
function q18(symbol : integer) : boolean; forward;
function q19(symbol : integer) : boolean; forward;
function q20(symbol : integer) : boolean; forward;
function q21(symbol : integer) : boolean; forward;
function q22(symbol : integer) : boolean; forward;
function q23(symbol : integer) : boolean; forward;
function q24(symbol : integer) : boolean; forward;
function q25(symbol : integer) : boolean; forward;
function q26(symbol : integer) : boolean; forward;
function q27(symbol : integer) : boolean; forward;
function q28(symbol : integer) : boolean; forward;
function q29(symbol : integer) : boolean; forward;
function q30(symbol : integer) : boolean; forward;
function q31(symbol : integer) : boolean; forward;
function q32(symbol : integer) : boolean; forward;
function q33(symbol : integer) : boolean; forward;
function q34(symbol : integer) : boolean; forward;
function q35(symbol : integer) : boolean; forward;

var
  (**
   * Sentenca
   *)
  sentence : string;

(**
 * Imprimir a execucao do automato finito deterministico
 *
 * @param state estado corrente
 * @param symbol simbolo corrente
 *)
procedure console(state : integer; symbol : integer);
var i : integer;
begin
  writeln();

  if state < 10 then
  begin
    write('q', state, '  - ');
  end
  else
  begin
    write('q', state, ' - ');
  end;

  for i := 1 to ord(sentence[0]) do
  begin
    if i <> symbol then
    begin
      write(' ', sentence[i], ' ');
    end
    else
    begin
      write('[', sentence[i], ']');
    end;
  end;
end;

(**
 * Estado q0 (inicial)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q0(symbol : integer) : boolean;
begin
  console(0, symbol);

  case sentence[symbol] of
    'a' : q0 := q1(symbol + 1);
    'b' : q0 := q4(symbol + 1);
    'd' : q0 := q7(symbol + 1);
    else  q0 := REJEITA;
  end;
end;

(**
 * Estado q1
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q1(symbol : integer) : boolean;
begin
  console(1, symbol);

  case sentence[symbol] of
    'b' : q1 := q2(symbol + 1);
    else  q1 := REJEITA;
  end;
end;

(**
 * Estado q2
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q2(symbol : integer) : boolean;
begin
  console(2, symbol);

  case sentence[symbol] of
    'c' : q2 := q3(symbol + 1);
    else  q2 := REJEITA;
  end;
end;

(**
 * Estado q3
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q3(symbol : integer) : boolean;
begin
  console(3, symbol);

  case sentence[symbol] of
    'd' : q3 := q10(symbol + 1);
    else  q3 := REJEITA;
  end;
end;

(**
 * Estado q4
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q4(symbol : integer) : boolean;
begin
  console(4, symbol);

  case sentence[symbol] of
    'a' : q4 := q5(symbol + 1);
    else  q4 := REJEITA;
  end;
end;

(**
 * Estado q5
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q5(symbol : integer) : boolean;
begin
  console(5, symbol);

  case sentence[symbol] of
    'b' : q5 := q6(symbol + 1);
    else  q5 := REJEITA;
  end;
end;

(**
 * Estado q6
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q6(symbol : integer) : boolean;
begin
  console(6, symbol);

  case sentence[symbol] of
    'a' : q6 := q16(symbol + 1);
    else  q6 := REJEITA;
  end;
end;

(**
 * Estado q7
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q7(symbol : integer) : boolean;
begin
  console(7, symbol);

  case sentence[symbol] of
    'c' : q7 := q8(symbol + 1);
    else  q7 := REJEITA;
  end;
end;

(**
 * Estado q8
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q8(symbol : integer) : boolean;
begin
  console(8, symbol);

  case sentence[symbol] of
    'b' : q8 := q9(symbol + 1);
    else  q8 := REJEITA;
  end;
end;

(**
 * Estado q9
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q9(symbol : integer) : boolean;
begin
  console(9, symbol);

  case sentence[symbol] of
    'a' : q9 := q16(symbol + 1);
    else  q9 := REJEITA;
  end;
end;

(**
 * Estado q10
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q10(symbol : integer) : boolean;
begin
  console(10, symbol);

  case sentence[symbol] of
    'a' : q10 := q11(symbol + 1);
    'b' : q10 := q15(symbol + 1);
    'c' : q10 := q19(symbol + 1);
    'd' : q10 := q10(symbol + 1);
    else  q10 := REJEITA;
  end;
end;

(**
 * Estado q11
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q11(symbol : integer) : boolean;
begin
  console(11, symbol);

  case sentence[symbol] of
    'a' : q11 := q11(symbol + 1);
    'b' : q11 := q12(symbol + 1);
    'c' : q11 := q19(symbol + 1);
    'd' : q11 := q10(symbol + 1);
    else  q11 := REJEITA;
  end;
end;

(**
 * Estado q12
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q12(symbol : integer) : boolean;
begin
  console(12, symbol);

  case sentence[symbol] of
    'a' : q12 := q16(symbol + 1);
    'b' : q12 := q15(symbol + 1);
    'c' : q12 := q13(symbol + 1);
    'd' : q12 := q10(symbol + 1);
    else  q12 := REJEITA;
  end;
end;

(**
 * Estado q13
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q13(symbol : integer) : boolean;
begin
  console(13, symbol);

  case sentence[symbol] of
    'a' : q13 := q11(symbol + 1);
    'b' : q13 := q14(symbol + 1);
    'c' : q13 := q20(symbol + 1);
    'd' : q13 := q10(symbol + 1);
    else  q13 := REJEITA;
  end;
end;

(**
 * Estado q14
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q14(symbol : integer) : boolean;
begin
  console(14, symbol);

  case sentence[symbol] of
    'a' : q14 := q16(symbol + 1);
    'b' : q14 := q15(symbol + 1);
    'c' : q14 := q25(symbol + 1);
    'd' : q14 := q10(symbol + 1);
    else  q14 := REJEITA;
  end;
end;

(**
 * Estado q15
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q15(symbol : integer) : boolean;
begin
  console(15, symbol);

  case sentence[symbol] of
    'a' : q15 := q16(symbol + 1);
    'b' : q15 := q15(symbol + 1);
    'c' : q15 := q19(symbol + 1);
    'd' : q15 := q10(symbol + 1);
    else  q15 := REJEITA;
  end;
end;

(**
 * Estado q16
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q16(symbol : integer) : boolean;
begin
  console(16, symbol);

  case sentence[symbol] of
    'a' : q16 := q11(symbol + 1);
    'b' : q16 := q12(symbol + 1);
    'c' : q16 := q19(symbol + 1);
    'd' : q16 := q17(symbol + 1);
    else  q16 := REJEITA;
  end;
end;

(**
 * Estado q17
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q17(symbol : integer) : boolean;
begin
  console(17, symbol);

  case sentence[symbol] of
    'a' : q17 := q11(symbol + 1);
    'b' : q17 := q15(symbol + 1);
    'c' : q17 := q18(symbol + 1);
    'd' : q17 := q10(symbol + 1);
    else  q17 := REJEITA;
  end;
end;

(**
 * Estado q18
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q18(symbol : integer) : boolean;
begin
  console(18, symbol);

  case sentence[symbol] of
    'a' : q18 := q11(symbol + 1);
    'b' : q18 := q15(symbol + 1);
    'c' : q18 := q20(symbol + 1);
    'd' : q18 := q29(symbol + 1);
    else  q18 := REJEITA;
  end;
end;

(**
 * Estado q19
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q19(symbol : integer) : boolean;
begin
  console(19, symbol);

  case sentence[symbol] of
    'a' : q19 := q11(symbol + 1);
    'b' : q19 := q15(symbol + 1);
    'c' : q19 := q20(symbol + 1);
    'd' : q19 := q10(symbol + 1);
    else  q19 := REJEITA;
  end;
end;

(**
 * Estado q20
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q20(symbol : integer) : boolean;
begin
  console(20, symbol);

  case sentence[symbol] of
    'a' : q20 := q11(symbol + 1);
    'b' : q20 := q15(symbol + 1);
    'c' : q20 := q20(symbol + 1);
    'd' : q20 := q21(symbol + 1);
    else  q20 := REJEITA;
  end;
end;

(**
 * Estado q21
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q21(symbol : integer) : boolean;
begin
  console(21, symbol);

  case sentence[symbol] of
    'a' : q21 := q22(symbol + 1);
    'b' : q21 := q15(symbol + 1);
    'c' : q21 := q19(symbol + 1);
    'd' : q21 := q10(symbol + 1);
    else  q21 := REJEITA;
  end;
end;

(**
 * Estado q22
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q22(symbol : integer) : boolean;
begin
  console(22, symbol);

  case sentence[symbol] of
    'a' : q22 := q11(symbol + 1);
    'b' : q22 := q34(symbol + 1);
    'c' : q22 := q19(symbol + 1);
    'd' : q22 := q10(symbol + 1);
    else  q22 := REJEITA;
  end;
end;

(**
 * Estado q23
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q23(symbol : integer) : boolean;
begin
  console(23, symbol);

  case sentence[symbol] of
    'a' : q23 := q23(symbol + 1);
    'b' : q23 := q24(symbol + 1);
    'c' : q23 := q28(symbol + 1);
    'd' : q23 := q32(symbol + 1);
    else  q23 := REJEITA;
  end;
end;

(**
 * Estado q24
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q24(symbol : integer) : boolean;
begin
  console(24, symbol);

  case sentence[symbol] of
    'a' : q24 := q23(symbol + 1);
    'b' : q24 := q24(symbol + 1);
    'c' : q24 := q25(symbol + 1);
    'd' : q24 := q32(symbol + 1);
    else  q24 := REJEITA;
  end;
end;

(**
 * Estado q25
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q25(symbol : integer) : boolean;
begin
  console(25, symbol);

  case sentence[symbol] of
    'a' : q25 := q23(symbol + 1);
    'b' : q25 := q24(symbol + 1);
    'c' : q25 := q26(symbol + 1);
    'd' : q25 := q29(symbol + 1);
    else  q25 := REJEITA;
  end;
end;

(**
 * Estado q26
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q26(symbol : integer) : boolean;
begin
  console(26, symbol);

  case sentence[symbol] of
    'a' : q26 := q27(symbol + 1);
    'b' : q26 := q24(symbol + 1);
    'c' : q26 := q28(symbol + 1);
    'd' : q26 := q29(symbol + 1);
    else  q26 := REJEITA;
  end;
end;

(**
 * Estado q27 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q27(symbol : integer) : boolean;
begin
  console(27, symbol);

  case sentence[symbol] of
    'a' : q27 := q23(symbol + 1);
    'b' : q27 := q24(symbol + 1);
    'c' : q27 := q28(symbol + 1);
    'd' : q27 := q32(symbol + 1);
    '$' : q27 := ACEITA;
    else  q27 := REJEITA;
  end;
end;

(**
 * Estado q28
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q28(symbol : integer) : boolean;
begin
  console(28, symbol);

  case sentence[symbol] of
    'a' : q28 := q23(symbol + 1);
    'b' : q28 := q24(symbol + 1);
    'c' : q28 := q28(symbol + 1);
    'd' : q28 := q29(symbol + 1);
    else  q28 := REJEITA;
  end;
end;

(**
 * Estado q29
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q29(symbol : integer) : boolean;
begin
  console(29, symbol);

  case sentence[symbol] of
    'a' : q29 := q30(symbol + 1);
    'b' : q29 := q24(symbol + 1);
    'c' : q29 := q28(symbol + 1);
    'd' : q29 := q32(symbol + 1);
    else  q29 := REJEITA;
  end;
end;

(**
 * Estado q30
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q30(symbol : integer) : boolean;
begin
  console(30, symbol);

  case sentence[symbol] of
    'a' : q30 := q23(symbol + 1);
    'b' : q30 := q24(symbol + 1);
    'c' : q30 := q31(symbol + 1);
    'd' : q30 := q32(symbol + 1);
    else  q30 := REJEITA;
  end;
end;

(**
 * Estado q31 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q31(symbol : integer) : boolean;
begin
  console(31, symbol);

  case sentence[symbol] of
    'a' : q31 := q23(symbol + 1);
    'b' : q31 := q24(symbol + 1);
    'c' : q31 := q28(symbol + 1);
    'd' : q31 := q29(symbol + 1);
    '$' : q31 := ACEITA;
    else  q31 := REJEITA;
  end;
end;

(**
 * Estado q32
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q32(symbol : integer) : boolean;
begin
  console(32, symbol);

  case sentence[symbol] of
    'a' : q32 := q33(symbol + 1);
    'b' : q32 := q24(symbol + 1);
    'c' : q32 := q28(symbol + 1);
    'd' : q32 := q32(symbol + 1);
    else  q32 := REJEITA;
  end;
end;

(**
 * Estado q33
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q33(symbol : integer) : boolean;
begin
  console(33, symbol);

  case sentence[symbol] of
    'a' : q33 := q23(symbol + 1);
    'b' : q33 := q34(symbol + 1);
    'c' : q33 := q28(symbol + 1);
    'd' : q33 := q32(symbol + 1);
    else  q33 := REJEITA;
  end;
end;

(**
 * Estado q34
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q34(symbol : integer) : boolean;
begin
  console(34, symbol);

  case sentence[symbol] of
    'a' : q34 := q23(symbol + 1);
    'b' : q34 := q24(symbol + 1);
    'c' : q34 := q35(symbol + 1);
    'd' : q34 := q32(symbol + 1);
    else  q34 := REJEITA;
  end;
end;

(**
 * Estado q35 (final)
 *
 * @param symbol simbolo corrente
 * @return ACEITA ou REJEITA
 *)
function q35(symbol : integer) : boolean;
begin
  console(35, symbol);

  case sentence[symbol] of
    'a' : q35 := q23(symbol + 1);
    'b' : q35 := q24(symbol + 1);
    'c' : q35 := q26(symbol + 1);
    'd' : q35 := q29(symbol + 1);
    '$' : q35 := ACEITA;
    else  q35 := REJEITA;
  end;
end;

(**
 * Metodo principal da linguagem de programacao Pascal
 *)
begin
  write('Analise a sentença: ');
  readln(sentence);

  if pos('$', sentence) <> 0 then
  begin
    writeln('A sentença "', sentence, '" é inválida');
    halt;
  end;

  sentence := sentence + '$';

  write('Observação: "$" representa o fim da sentença');

  if q0(1) then
  begin
    writeln(' - ACEITA');
  end
  else
  begin
    writeln(' - REJEITA');
  end;
end.