Ybadoo - Soluções em Software Livre
Tutoriais
Linguagens Formais e Autômatos

Desenvolva um autômato finito determinístico sobre o alfabeto Σ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z} que reconheça a linguagem L = {w | w possui jogatina ou jogo ou sensual ou sex como subpalavra}.

 

M = ({a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14}, δ, q0, {q14})

Grafo com a função de transição de M
Grafo com a função de transição de M
Tabela com a função de transição de M
δabcdefghijklmnopqrstuvwxyz
q0q0q0q0q0q0q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q1q0q0q0q0q0q0q0q0q0q1q0q0q0q0q2q0q0q0q8q0q0q0q0q0q0q0
q2q0q0q0q0q0q0q3q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q3q4q0q0q0q0q0q0q0q0q1q0q0q0q0q14q0q0q0q8q0q0q0q0q0q0q0
q4q0q0q0q0q0q0q0q0q0q1q0q0q0q0q0q0q0q0q8q5q0q0q0q0q0q0
q5q0q0q0q0q0q0q0q0q6q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q6q0q0q0q0q0q0q0q0q0q1q0q0q0q7q0q0q0q0q8q0q0q0q0q0q0q0
q7q14q0q0q0q0q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q8q0q0q0q0q9q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q9q0q0q0q0q0q0q0q0q0q1q0q0q0q10q0q0q0q0q8q0q0q0q0q14q0q0
q10q0q0q0q0q0q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q11q0q0q0q0q9q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q12q0q0q0q0q0
q12q13q0q0q0q0q0q0q0q0q1q0q0q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q13q0q0q0q0q0q0q0q0q0q1q0q14q0q0q0q0q0q0q8q0q0q0q0q0q0q0
q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14q14

Terminal

ybadoo@server:~$ ./application
Implementação na linguagem de programação Java Implementação na linguagem de programação C++ Implementação na linguagem de programação C Implementação na linguagem de programação Pascal
Diagrama de classes na linguagem de programação Java State.java DeterministicFiniteAutomaton.java Application.java
Diagrama de classes na linguagem de programação Java
Diagrama de classes na linguagem de programação Java

Arquivo State.java

/*************************************************************************
 * Copyright (C) 2009/2018 - 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.exercicio240;

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);
  }
}

Arquivo DeterministicFiniteAutomaton.java

/*************************************************************************
 * Copyright (C) 2009/2018 - 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.exercicio240;

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', 0);
    q0.addTransition('b', 0);
    q0.addTransition('c', 0);
    q0.addTransition('d', 0);
    q0.addTransition('e', 0);
    q0.addTransition('f', 0);
    q0.addTransition('g', 0);
    q0.addTransition('h', 0);
    q0.addTransition('i', 0);
    q0.addTransition('j', 1);
    q0.addTransition('k', 0);
    q0.addTransition('l', 0);
    q0.addTransition('m', 0);
    q0.addTransition('n', 0);
    q0.addTransition('o', 0);
    q0.addTransition('p', 0);
    q0.addTransition('q', 0);
    q0.addTransition('r', 0);
    q0.addTransition('s', 8);
    q0.addTransition('t', 0);
    q0.addTransition('u', 0);
    q0.addTransition('v', 0);
    q0.addTransition('w', 0);
    q0.addTransition('x', 0);
    q0.addTransition('y', 0);
    q0.addTransition('z', 0);
    states.put(0, q0);

    State q1 = new State(false);
    q1.addTransition('a', 0);
    q1.addTransition('b', 0);
    q1.addTransition('c', 0);
    q1.addTransition('d', 0);
    q1.addTransition('e', 0);
    q1.addTransition('f', 0);
    q1.addTransition('g', 0);
    q1.addTransition('h', 0);
    q1.addTransition('i', 0);
    q1.addTransition('j', 1);
    q1.addTransition('k', 0);
    q1.addTransition('l', 0);
    q1.addTransition('m', 0);
    q1.addTransition('n', 0);
    q1.addTransition('o', 2);
    q1.addTransition('p', 0);
    q1.addTransition('q', 0);
    q1.addTransition('r', 0);
    q1.addTransition('s', 8);
    q1.addTransition('t', 0);
    q1.addTransition('u', 0);
    q1.addTransition('v', 0);
    q1.addTransition('w', 0);
    q1.addTransition('x', 0);
    q1.addTransition('y', 0);
    q1.addTransition('z', 0);
    states.put(1, q1);

    State q2 = new State(false);
    q2.addTransition('a', 0);
    q2.addTransition('b', 0);
    q2.addTransition('c', 0);
    q2.addTransition('d', 0);
    q2.addTransition('e', 0);
    q2.addTransition('f', 0);
    q2.addTransition('g', 3);
    q2.addTransition('h', 0);
    q2.addTransition('i', 0);
    q2.addTransition('j', 1);
    q2.addTransition('k', 0);
    q2.addTransition('l', 0);
    q2.addTransition('m', 0);
    q2.addTransition('n', 0);
    q2.addTransition('o', 0);
    q2.addTransition('p', 0);
    q2.addTransition('q', 0);
    q2.addTransition('r', 0);
    q2.addTransition('s', 8);
    q2.addTransition('t', 0);
    q2.addTransition('u', 0);
    q2.addTransition('v', 0);
    q2.addTransition('w', 0);
    q2.addTransition('x', 0);
    q2.addTransition('y', 0);
    q2.addTransition('z', 0);
    states.put(2, q2);

    State q3 = new State(false);
    q3.addTransition('a', 4);
    q3.addTransition('b', 0);
    q3.addTransition('c', 0);
    q3.addTransition('d', 0);
    q3.addTransition('e', 0);
    q3.addTransition('f', 0);
    q3.addTransition('g', 0);
    q3.addTransition('h', 0);
    q3.addTransition('i', 0);
    q3.addTransition('j', 1);
    q3.addTransition('k', 0);
    q3.addTransition('l', 0);
    q3.addTransition('m', 0);
    q3.addTransition('n', 0);
    q3.addTransition('o', 14);
    q3.addTransition('p', 0);
    q3.addTransition('q', 0);
    q3.addTransition('r', 0);
    q3.addTransition('s', 8);
    q3.addTransition('t', 0);
    q3.addTransition('u', 0);
    q3.addTransition('v', 0);
    q3.addTransition('w', 0);
    q3.addTransition('x', 0);
    q3.addTransition('y', 0);
    q3.addTransition('z', 0);
    states.put(3, q3);

    State q4 = new State(false);
    q4.addTransition('a', 0);
    q4.addTransition('b', 0);
    q4.addTransition('c', 0);
    q4.addTransition('d', 0);
    q4.addTransition('e', 0);
    q4.addTransition('f', 0);
    q4.addTransition('g', 0);
    q4.addTransition('h', 0);
    q4.addTransition('i', 0);
    q4.addTransition('j', 1);
    q4.addTransition('k', 0);
    q4.addTransition('l', 0);
    q4.addTransition('m', 0);
    q4.addTransition('n', 0);
    q4.addTransition('o', 0);
    q4.addTransition('p', 0);
    q4.addTransition('q', 0);
    q4.addTransition('r', 0);
    q4.addTransition('s', 8);
    q4.addTransition('t', 5);
    q4.addTransition('u', 0);
    q4.addTransition('v', 0);
    q4.addTransition('w', 0);
    q4.addTransition('x', 0);
    q4.addTransition('y', 0);
    q4.addTransition('z', 0);
    states.put(4, q4);

    State q5 = new State(false);
    q5.addTransition('a', 0);
    q5.addTransition('b', 0);
    q5.addTransition('c', 0);
    q5.addTransition('d', 0);
    q5.addTransition('e', 0);
    q5.addTransition('f', 0);
    q5.addTransition('g', 0);
    q5.addTransition('h', 0);
    q5.addTransition('i', 6);
    q5.addTransition('j', 1);
    q5.addTransition('k', 0);
    q5.addTransition('l', 0);
    q5.addTransition('m', 0);
    q5.addTransition('n', 0);
    q5.addTransition('o', 0);
    q5.addTransition('p', 0);
    q5.addTransition('q', 0);
    q5.addTransition('r', 0);
    q5.addTransition('s', 8);
    q5.addTransition('t', 0);
    q5.addTransition('u', 0);
    q5.addTransition('v', 0);
    q5.addTransition('w', 0);
    q5.addTransition('x', 0);
    q5.addTransition('y', 0);
    q5.addTransition('z', 0);
    states.put(5, q5);

    State q6 = new State(false);
    q6.addTransition('a', 0);
    q6.addTransition('b', 0);
    q6.addTransition('c', 0);
    q6.addTransition('d', 0);
    q6.addTransition('e', 0);
    q6.addTransition('f', 0);
    q6.addTransition('g', 0);
    q6.addTransition('h', 0);
    q6.addTransition('i', 0);
    q6.addTransition('j', 1);
    q6.addTransition('k', 0);
    q6.addTransition('l', 0);
    q6.addTransition('m', 0);
    q6.addTransition('n', 7);
    q6.addTransition('o', 0);
    q6.addTransition('p', 0);
    q6.addTransition('q', 0);
    q6.addTransition('r', 0);
    q6.addTransition('s', 8);
    q6.addTransition('t', 0);
    q6.addTransition('u', 0);
    q6.addTransition('v', 0);
    q6.addTransition('w', 0);
    q6.addTransition('x', 0);
    q6.addTransition('y', 0);
    q6.addTransition('z', 0);
    states.put(6, q6);

    State q7 = new State(false);
    q7.addTransition('a', 14);
    q7.addTransition('b', 0);
    q7.addTransition('c', 0);
    q7.addTransition('d', 0);
    q7.addTransition('e', 0);
    q7.addTransition('f', 0);
    q7.addTransition('g', 0);
    q7.addTransition('h', 0);
    q7.addTransition('i', 0);
    q7.addTransition('j', 1);
    q7.addTransition('k', 0);
    q7.addTransition('l', 0);
    q7.addTransition('m', 0);
    q7.addTransition('n', 0);
    q7.addTransition('o', 0);
    q7.addTransition('p', 0);
    q7.addTransition('q', 0);
    q7.addTransition('r', 0);
    q7.addTransition('s', 8);
    q7.addTransition('t', 0);
    q7.addTransition('u', 0);
    q7.addTransition('v', 0);
    q7.addTransition('w', 0);
    q7.addTransition('x', 0);
    q7.addTransition('y', 0);
    q7.addTransition('z', 0);
    states.put(7, q7);

    State q8 = new State(false);
    q8.addTransition('a', 0);
    q8.addTransition('b', 0);
    q8.addTransition('c', 0);
    q8.addTransition('d', 0);
    q8.addTransition('e', 9);
    q8.addTransition('f', 0);
    q8.addTransition('g', 0);
    q8.addTransition('h', 0);
    q8.addTransition('i', 0);
    q8.addTransition('j', 1);
    q8.addTransition('k', 0);
    q8.addTransition('l', 0);
    q8.addTransition('m', 0);
    q8.addTransition('n', 0);
    q8.addTransition('o', 0);
    q8.addTransition('p', 0);
    q8.addTransition('q', 0);
    q8.addTransition('r', 0);
    q8.addTransition('s', 8);
    q8.addTransition('t', 0);
    q8.addTransition('u', 0);
    q8.addTransition('v', 0);
    q8.addTransition('w', 0);
    q8.addTransition('x', 0);
    q8.addTransition('y', 0);
    q8.addTransition('z', 0);
    states.put(8, q8);

    State q9 = new State(false);
    q9.addTransition('a', 0);
    q9.addTransition('b', 0);
    q9.addTransition('c', 0);
    q9.addTransition('d', 0);
    q9.addTransition('e', 0);
    q9.addTransition('f', 0);
    q9.addTransition('g', 0);
    q9.addTransition('h', 0);
    q9.addTransition('i', 0);
    q9.addTransition('j', 1);
    q9.addTransition('k', 0);
    q9.addTransition('l', 0);
    q9.addTransition('m', 0);
    q9.addTransition('n', 10);
    q9.addTransition('o', 0);
    q9.addTransition('p', 0);
    q9.addTransition('q', 0);
    q9.addTransition('r', 0);
    q9.addTransition('s', 8);
    q9.addTransition('t', 0);
    q9.addTransition('u', 0);
    q9.addTransition('v', 0);
    q9.addTransition('w', 0);
    q9.addTransition('x', 14);
    q9.addTransition('y', 0);
    q9.addTransition('z', 0);
    states.put(9, q9);

    State q10 = new State(false);
    q10.addTransition('a', 0);
    q10.addTransition('b', 0);
    q10.addTransition('c', 0);
    q10.addTransition('d', 0);
    q10.addTransition('e', 0);
    q10.addTransition('f', 0);
    q10.addTransition('g', 0);
    q10.addTransition('h', 0);
    q10.addTransition('i', 0);
    q10.addTransition('j', 1);
    q10.addTransition('k', 0);
    q10.addTransition('l', 0);
    q10.addTransition('m', 0);
    q10.addTransition('n', 0);
    q10.addTransition('o', 0);
    q10.addTransition('p', 0);
    q10.addTransition('q', 0);
    q10.addTransition('r', 0);
    q10.addTransition('s', 8);
    q10.addTransition('t', 0);
    q10.addTransition('u', 0);
    q10.addTransition('v', 0);
    q10.addTransition('w', 0);
    q10.addTransition('x', 0);
    q10.addTransition('y', 0);
    q10.addTransition('z', 0);
    states.put(10, q10);

    State q11 = new State(false);
    q11.addTransition('a', 0);
    q11.addTransition('b', 0);
    q11.addTransition('c', 0);
    q11.addTransition('d', 0);
    q11.addTransition('e', 9);
    q11.addTransition('f', 0);
    q11.addTransition('g', 0);
    q11.addTransition('h', 0);
    q11.addTransition('i', 0);
    q11.addTransition('j', 1);
    q11.addTransition('k', 0);
    q11.addTransition('l', 0);
    q11.addTransition('m', 0);
    q11.addTransition('n', 0);
    q11.addTransition('o', 0);
    q11.addTransition('p', 0);
    q11.addTransition('q', 0);
    q11.addTransition('r', 0);
    q11.addTransition('s', 8);
    q11.addTransition('t', 0);
    q11.addTransition('u', 12);
    q11.addTransition('v', 0);
    q11.addTransition('w', 0);
    q11.addTransition('x', 0);
    q11.addTransition('y', 0);
    q11.addTransition('z', 0);
    states.put(11, q11);

    State q12 = new State(false);
    q12.addTransition('a', 13);
    q12.addTransition('b', 0);
    q12.addTransition('c', 0);
    q12.addTransition('d', 0);
    q12.addTransition('e', 0);
    q12.addTransition('f', 0);
    q12.addTransition('g', 0);
    q12.addTransition('h', 0);
    q12.addTransition('i', 0);
    q12.addTransition('j', 1);
    q12.addTransition('k', 0);
    q12.addTransition('l', 0);
    q12.addTransition('m', 0);
    q12.addTransition('n', 0);
    q12.addTransition('o', 0);
    q12.addTransition('p', 0);
    q12.addTransition('q', 0);
    q12.addTransition('r', 0);
    q12.addTransition('s', 8);
    q12.addTransition('t', 0);
    q12.addTransition('u', 0);
    q12.addTransition('v', 0);
    q12.addTransition('w', 0);
    q12.addTransition('x', 0);
    q12.addTransition('y', 0);
    q12.addTransition('z', 0);
    states.put(12, q12);

    State q13 = new State(false);
    q13.addTransition('a', 0);
    q13.addTransition('b', 0);
    q13.addTransition('c', 0);
    q13.addTransition('d', 0);
    q13.addTransition('e', 0);
    q13.addTransition('f', 0);
    q13.addTransition('g', 0);
    q13.addTransition('h', 0);
    q13.addTransition('i', 0);
    q13.addTransition('j', 1);
    q13.addTransition('k', 0);
    q13.addTransition('l', 14);
    q13.addTransition('m', 0);
    q13.addTransition('n', 0);
    q13.addTransition('o', 0);
    q13.addTransition('p', 0);
    q13.addTransition('q', 0);
    q13.addTransition('r', 0);
    q13.addTransition('s', 8);
    q13.addTransition('t', 0);
    q13.addTransition('u', 0);
    q13.addTransition('v', 0);
    q13.addTransition('w', 0);
    q13.addTransition('x', 0);
    q13.addTransition('y', 0);
    q13.addTransition('z', 0);
    states.put(13, q13);

    State q14 = new State(true);
    q14.addTransition('a', 14);
    q14.addTransition('b', 14);
    q14.addTransition('c', 14);
    q14.addTransition('d', 14);
    q14.addTransition('e', 14);
    q14.addTransition('f', 14);
    q14.addTransition('g', 14);
    q14.addTransition('h', 14);
    q14.addTransition('i', 14);
    q14.addTransition('j', 14);
    q14.addTransition('k', 14);
    q14.addTransition('l', 14);
    q14.addTransition('m', 14);
    q14.addTransition('n', 14);
    q14.addTransition('o', 14);
    q14.addTransition('p', 14);
    q14.addTransition('q', 14);
    q14.addTransition('r', 14);
    q14.addTransition('s', 14);
    q14.addTransition('t', 14);
    q14.addTransition('u', 14);
    q14.addTransition('v', 14);
    q14.addTransition('w', 14);
    q14.addTransition('x', 14);
    q14.addTransition('y', 14);
    q14.addTransition('z', 14);
    q14.addTransition('$', 14);
    states.put(14, q14);
  }

  /**
   * 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();
  }
}

Arquivo Application.java

/*************************************************************************
 * Copyright (C) 2009/2018 - 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.exercicio240;

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);
  }
}
Diagrama de classes na linguagem de programação C++ State.hpp State.cpp DeterministicFiniteAutomaton.hpp DeterministicFiniteAutomaton.cpp Application.cpp Makefile para a linguagem de programação C++
Diagrama de classes na linguagem de programação C++
Diagrama de classes na linguagem de programação C++

Arquivo State.hpp

/*************************************************************************
 * Copyright (C) 2009/2018 - 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

Arquivo State.cpp

/*************************************************************************
 * Copyright (C) 2009/2018 - 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;
}

Arquivo DeterministicFiniteAutomaton.hpp

/*************************************************************************
 * Copyright (C) 2009/2018 - 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

Arquivo DeterministicFiniteAutomaton.cpp

/*************************************************************************
 * Copyright (C) 2009/2018 - 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', 0);
  q0->addTransition('b', 0);
  q0->addTransition('c', 0);
  q0->addTransition('d', 0);
  q0->addTransition('e', 0);
  q0->addTransition('f', 0);
  q0->addTransition('g', 0);
  q0->addTransition('h', 0);
  q0->addTransition('i', 0);
  q0->addTransition('j', 1);
  q0->addTransition('k', 0);
  q0->addTransition('l', 0);
  q0->addTransition('m', 0);
  q0->addTransition('n', 0);
  q0->addTransition('o', 0);
  q0->addTransition('p', 0);
  q0->addTransition('q', 0);
  q0->addTransition('r', 0);
  q0->addTransition('s', 8);
  q0->addTransition('t', 0);
  q0->addTransition('u', 0);
  q0->addTransition('v', 0);
  q0->addTransition('w', 0);
  q0->addTransition('x', 0);
  q0->addTransition('y', 0);
  q0->addTransition('z', 0);
  states->insert(std::pair<int, State*>(0, q0));

  State* q1 = new State(false);
  q1->addTransition('a', 0);
  q1->addTransition('b', 0);
  q1->addTransition('c', 0);
  q1->addTransition('d', 0);
  q1->addTransition('e', 0);
  q1->addTransition('f', 0);
  q1->addTransition('g', 0);
  q1->addTransition('h', 0);
  q1->addTransition('i', 0);
  q1->addTransition('j', 1);
  q1->addTransition('k', 0);
  q1->addTransition('l', 0);
  q1->addTransition('m', 0);
  q1->addTransition('n', 0);
  q1->addTransition('o', 2);
  q1->addTransition('p', 0);
  q1->addTransition('q', 0);
  q1->addTransition('r', 0);
  q1->addTransition('s', 8);
  q1->addTransition('t', 0);
  q1->addTransition('u', 0);
  q1->addTransition('v', 0);
  q1->addTransition('w', 0);
  q1->addTransition('x', 0);
  q1->addTransition('y', 0);
  q1->addTransition('z', 0);
  states->insert(std::pair<int, State*>(1, q1));

  State* q2 = new State(false);
  q2->addTransition('a', 0);
  q2->addTransition('b', 0);
  q2->addTransition('c', 0);
  q2->addTransition('d', 0);
  q2->addTransition('e', 0);
  q2->addTransition('f', 0);
  q2->addTransition('g', 3);
  q2->addTransition('h', 0);
  q2->addTransition('i', 0);
  q2->addTransition('j', 1);
  q2->addTransition('k', 0);
  q2->addTransition('l', 0);
  q2->addTransition('m', 0);
  q2->addTransition('n', 0);
  q2->addTransition('o', 0);
  q2->addTransition('p', 0);
  q2->addTransition('q', 0);
  q2->addTransition('r', 0);
  q2->addTransition('s', 8);
  q2->addTransition('t', 0);
  q2->addTransition('u', 0);
  q2->addTransition('v', 0);
  q2->addTransition('w', 0);
  q2->addTransition('x', 0);
  q2->addTransition('y', 0);
  q2->addTransition('z', 0);
  states->insert(std::pair<int, State*>(2, q2));

  State* q3 = new State(false);
  q3->addTransition('a', 4);
  q3->addTransition('b', 0);
  q3->addTransition('c', 0);
  q3->addTransition('d', 0);
  q3->addTransition('e', 0);
  q3->addTransition('f', 0);
  q3->addTransition('g', 0);
  q3->addTransition('h', 0);
  q3->addTransition('i', 0);
  q3->addTransition('j', 1);
  q3->addTransition('k', 0);
  q3->addTransition('l', 0);
  q3->addTransition('m', 0);
  q3->addTransition('n', 0);
  q3->addTransition('o', 14);
  q3->addTransition('p', 0);
  q3->addTransition('q', 0);
  q3->addTransition('r', 0);
  q3->addTransition('s', 8);
  q3->addTransition('t', 0);
  q3->addTransition('u', 0);
  q3->addTransition('v', 0);
  q3->addTransition('w', 0);
  q3->addTransition('x', 0);
  q3->addTransition('y', 0);
  q3->addTransition('z', 0);
  states->insert(std::pair<int, State*>(3, q3));

  State* q4 = new State(false);
  q4->addTransition('a', 0);
  q4->addTransition('b', 0);
  q4->addTransition('c', 0);
  q4->addTransition('d', 0);
  q4->addTransition('e', 0);
  q4->addTransition('f', 0);
  q4->addTransition('g', 0);
  q4->addTransition('h', 0);
  q4->addTransition('i', 0);
  q4->addTransition('j', 1);
  q4->addTransition('k', 0);
  q4->addTransition('l', 0);
  q4->addTransition('m', 0);
  q4->addTransition('n', 0);
  q4->addTransition('o', 0);
  q4->addTransition('p', 0);
  q4->addTransition('q', 0);
  q4->addTransition('r', 0);
  q4->addTransition('s', 8);
  q4->addTransition('t', 5);
  q4->addTransition('u', 0);
  q4->addTransition('v', 0);
  q4->addTransition('w', 0);
  q4->addTransition('x', 0);
  q4->addTransition('y', 0);
  q4->addTransition('z', 0);
  states->insert(std::pair<int, State*>(4, q4));

  State* q5 = new State(false);
  q5->addTransition('a', 0);
  q5->addTransition('b', 0);
  q5->addTransition('c', 0);
  q5->addTransition('d', 0);
  q5->addTransition('e', 0);
  q5->addTransition('f', 0);
  q5->addTransition('g', 0);
  q5->addTransition('h', 0);
  q5->addTransition('i', 6);
  q5->addTransition('j', 1);
  q5->addTransition('k', 0);
  q5->addTransition('l', 0);
  q5->addTransition('m', 0);
  q5->addTransition('n', 0);
  q5->addTransition('o', 0);
  q5->addTransition('p', 0);
  q5->addTransition('q', 0);
  q5->addTransition('r', 0);
  q5->addTransition('s', 8);
  q5->addTransition('t', 0);
  q5->addTransition('u', 0);
  q5->addTransition('v', 0);
  q5->addTransition('w', 0);
  q5->addTransition('x', 0);
  q5->addTransition('y', 0);
  q5->addTransition('z', 0);
  states->insert(std::pair<int, State*>(5, q5));

  State* q6 = new State(false);
  q6->addTransition('a', 0);
  q6->addTransition('b', 0);
  q6->addTransition('c', 0);
  q6->addTransition('d', 0);
  q6->addTransition('e', 0);
  q6->addTransition('f', 0);
  q6->addTransition('g', 0);
  q6->addTransition('h', 0);
  q6->addTransition('i', 0);
  q6->addTransition('j', 1);
  q6->addTransition('k', 0);
  q6->addTransition('l', 0);
  q6->addTransition('m', 0);
  q6->addTransition('n', 7);
  q6->addTransition('o', 0);
  q6->addTransition('p', 0);
  q6->addTransition('q', 0);
  q6->addTransition('r', 0);
  q6->addTransition('s', 8);
  q6->addTransition('t', 0);
  q6->addTransition('u', 0);
  q6->addTransition('v', 0);
  q6->addTransition('w', 0);
  q6->addTransition('x', 0);
  q6->addTransition('y', 0);
  q6->addTransition('z', 0);
  states->insert(std::pair<int, State*>(6, q6));

  State* q7 = new State(false);
  q7->addTransition('a', 14);
  q7->addTransition('b', 0);
  q7->addTransition('c', 0);
  q7->addTransition('d', 0);
  q7->addTransition('e', 0);
  q7->addTransition('f', 0);
  q7->addTransition('g', 0);
  q7->addTransition('h', 0);
  q7->addTransition('i', 0);
  q7->addTransition('j', 1);
  q7->addTransition('k', 0);
  q7->addTransition('l', 0);
  q7->addTransition('m', 0);
  q7->addTransition('n', 0);
  q7->addTransition('o', 0);
  q7->addTransition('p', 0);
  q7->addTransition('q', 0);
  q7->addTransition('r', 0);
  q7->addTransition('s', 8);
  q7->addTransition('t', 0);
  q7->addTransition('u', 0);
  q7->addTransition('v', 0);
  q7->addTransition('w', 0);
  q7->addTransition('x', 0);
  q7->addTransition('y', 0);
  q7->addTransition('z', 0);
  states->insert(std::pair<int, State*>(7, q7));

  State* q8 = new State(false);
  q8->addTransition('a', 0);
  q8->addTransition('b', 0);
  q8->addTransition('c', 0);
  q8->addTransition('d', 0);
  q8->addTransition('e', 9);
  q8->addTransition('f', 0);
  q8->addTransition('g', 0);
  q8->addTransition('h', 0);
  q8->addTransition('i', 0);
  q8->addTransition('j', 1);
  q8->addTransition('k', 0);
  q8->addTransition('l', 0);
  q8->addTransition('m', 0);
  q8->addTransition('n', 0);
  q8->addTransition('o', 0);
  q8->addTransition('p', 0);
  q8->addTransition('q', 0);
  q8->addTransition('r', 0);
  q8->addTransition('s', 8);
  q8->addTransition('t', 0);
  q8->addTransition('u', 0);
  q8->addTransition('v', 0);
  q8->addTransition('w', 0);
  q8->addTransition('x', 0);
  q8->addTransition('y', 0);
  q8->addTransition('z', 0);
  states->insert(std::pair<int, State*>(8, q8));

  State* q9 = new State(false);
  q9->addTransition('a', 0);
  q9->addTransition('b', 0);
  q9->addTransition('c', 0);
  q9->addTransition('d', 0);
  q9->addTransition('e', 0);
  q9->addTransition('f', 0);
  q9->addTransition('g', 0);
  q9->addTransition('h', 0);
  q9->addTransition('i', 0);
  q9->addTransition('j', 1);
  q9->addTransition('k', 0);
  q9->addTransition('l', 0);
  q9->addTransition('m', 0);
  q9->addTransition('n', 10);
  q9->addTransition('o', 0);
  q9->addTransition('p', 0);
  q9->addTransition('q', 0);
  q9->addTransition('r', 0);
  q9->addTransition('s', 8);
  q9->addTransition('t', 0);
  q9->addTransition('u', 0);
  q9->addTransition('v', 0);
  q9->addTransition('w', 0);
  q9->addTransition('x', 14);
  q9->addTransition('y', 0);
  q9->addTransition('z', 0);
  states->insert(std::pair<int, State*>(9, q9));

  State* q10 = new State(false);
  q10->addTransition('a', 0);
  q10->addTransition('b', 0);
  q10->addTransition('c', 0);
  q10->addTransition('d', 0);
  q10->addTransition('e', 0);
  q10->addTransition('f', 0);
  q10->addTransition('g', 0);
  q10->addTransition('h', 0);
  q10->addTransition('i', 0);
  q10->addTransition('j', 1);
  q10->addTransition('k', 0);
  q10->addTransition('l', 0);
  q10->addTransition('m', 0);
  q10->addTransition('n', 0);
  q10->addTransition('o', 0);
  q10->addTransition('p', 0);
  q10->addTransition('q', 0);
  q10->addTransition('r', 0);
  q10->addTransition('s', 8);
  q10->addTransition('t', 0);
  q10->addTransition('u', 0);
  q10->addTransition('v', 0);
  q10->addTransition('w', 0);
  q10->addTransition('x', 0);
  q10->addTransition('y', 0);
  q10->addTransition('z', 0);
  states->insert(std::pair<int, State*>(10, q10));

  State* q11 = new State(false);
  q11->addTransition('a', 0);
  q11->addTransition('b', 0);
  q11->addTransition('c', 0);
  q11->addTransition('d', 0);
  q11->addTransition('e', 9);
  q11->addTransition('f', 0);
  q11->addTransition('g', 0);
  q11->addTransition('h', 0);
  q11->addTransition('i', 0);
  q11->addTransition('j', 1);
  q11->addTransition('k', 0);
  q11->addTransition('l', 0);
  q11->addTransition('m', 0);
  q11->addTransition('n', 0);
  q11->addTransition('o', 0);
  q11->addTransition('p', 0);
  q11->addTransition('q', 0);
  q11->addTransition('r', 0);
  q11->addTransition('s', 8);
  q11->addTransition('t', 0);
  q11->addTransition('u', 12);
  q11->addTransition('v', 0);
  q11->addTransition('w', 0);
  q11->addTransition('x', 0);
  q11->addTransition('y', 0);
  q11->addTransition('z', 0);
  states->insert(std::pair<int, State*>(11, q11));

  State* q12 = new State(false);
  q12->addTransition('a', 13);
  q12->addTransition('b', 0);
  q12->addTransition('c', 0);
  q12->addTransition('d', 0);
  q12->addTransition('e', 0);
  q12->addTransition('f', 0);
  q12->addTransition('g', 0);
  q12->addTransition('h', 0);
  q12->addTransition('i', 0);
  q12->addTransition('j', 1);
  q12->addTransition('k', 0);
  q12->addTransition('l', 0);
  q12->addTransition('m', 0);
  q12->addTransition('n', 0);
  q12->addTransition('o', 0);
  q12->addTransition('p', 0);
  q12->addTransition('q', 0);
  q12->addTransition('r', 0);
  q12->addTransition('s', 8);
  q12->addTransition('t', 0);
  q12->addTransition('u', 0);
  q12->addTransition('v', 0);
  q12->addTransition('w', 0);
  q12->addTransition('x', 0);
  q12->addTransition('y', 0);
  q12->addTransition('z', 0);
  states->insert(std::pair<int, State*>(12, q12));

  State* q13 = new State(false);
  q13->addTransition('a', 0);
  q13->addTransition('b', 0);
  q13->addTransition('c', 0);
  q13->addTransition('d', 0);
  q13->addTransition('e', 0);
  q13->addTransition('f', 0);
  q13->addTransition('g', 0);
  q13->addTransition('h', 0);
  q13->addTransition('i', 0);
  q13->addTransition('j', 1);
  q13->addTransition('k', 0);
  q13->addTransition('l', 14);
  q13->addTransition('m', 0);
  q13->addTransition('n', 0);
  q13->addTransition('o', 0);
  q13->addTransition('p', 0);
  q13->addTransition('q', 0);
  q13->addTransition('r', 0);
  q13->addTransition('s', 8);
  q13->addTransition('t', 0);
  q13->addTransition('u', 0);
  q13->addTransition('v', 0);
  q13->addTransition('w', 0);
  q13->addTransition('x', 0);
  q13->addTransition('y', 0);
  q13->addTransition('z', 0);
  states->insert(std::pair<int, State*>(13, q13));

  State* q14 = new State(true);
  q14->addTransition('a', 14);
  q14->addTransition('b', 14);
  q14->addTransition('c', 14);
  q14->addTransition('d', 14);
  q14->addTransition('e', 14);
  q14->addTransition('f', 14);
  q14->addTransition('g', 14);
  q14->addTransition('h', 14);
  q14->addTransition('i', 14);
  q14->addTransition('j', 14);
  q14->addTransition('k', 14);
  q14->addTransition('l', 14);
  q14->addTransition('m', 14);
  q14->addTransition('n', 14);
  q14->addTransition('o', 14);
  q14->addTransition('p', 14);
  q14->addTransition('q', 14);
  q14->addTransition('r', 14);
  q14->addTransition('s', 14);
  q14->addTransition('t', 14);
  q14->addTransition('u', 14);
  q14->addTransition('v', 14);
  q14->addTransition('w', 14);
  q14->addTransition('x', 14);
  q14->addTransition('y', 14);
  q14->addTransition('z', 14);
  q14->addTransition('$', 14);
  states->insert(std::pair<int, State*>(14, q14));
}

/**
 * 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();
}

Arquivo Application.cpp

/*************************************************************************
 * Copyright (C) 2009/2018 - 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;
}

Arquivo makefile

##########################################################################
 # Copyright (C) 2009/2018 - 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
DeterministicFiniteAutomaton.c Makefile para a linguagem de programação C

Arquivo DeterministicFiniteAutomaton.c

/*************************************************************************
 * Copyright (C) 2009/2018 - 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);

/**
 * 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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q2(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q3(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q4(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q14(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q5(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q6(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q7(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q14(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 'a': return q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q9(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q10(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q14(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q9(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q12(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q13(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q0(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(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 q0(symbol);
    case 'b': return q0(symbol);
    case 'c': return q0(symbol);
    case 'd': return q0(symbol);
    case 'e': return q0(symbol);
    case 'f': return q0(symbol);
    case 'g': return q0(symbol);
    case 'h': return q0(symbol);
    case 'i': return q0(symbol);
    case 'j': return q1(symbol);
    case 'k': return q0(symbol);
    case 'l': return q14(symbol);
    case 'm': return q0(symbol);
    case 'n': return q0(symbol);
    case 'o': return q0(symbol);
    case 'p': return q0(symbol);
    case 'q': return q0(symbol);
    case 'r': return q0(symbol);
    case 's': return q8(symbol);
    case 't': return q0(symbol);
    case 'u': return q0(symbol);
    case 'v': return q0(symbol);
    case 'w': return q0(symbol);
    case 'x': return q0(symbol);
    case 'y': return q0(symbol);
    case 'z': return q0(symbol);
    default : return REJEITA;
  }
}

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

  switch(sentence[symbol++])
  {
    case 'a': return q14(symbol);
    case 'b': return q14(symbol);
    case 'c': return q14(symbol);
    case 'd': return q14(symbol);
    case 'e': return q14(symbol);
    case 'f': return q14(symbol);
    case 'g': return q14(symbol);
    case 'h': return q14(symbol);
    case 'i': return q14(symbol);
    case 'j': return q14(symbol);
    case 'k': return q14(symbol);
    case 'l': return q14(symbol);
    case 'm': return q14(symbol);
    case 'n': return q14(symbol);
    case 'o': return q14(symbol);
    case 'p': return q14(symbol);
    case 'q': return q14(symbol);
    case 'r': return q14(symbol);
    case 's': return q14(symbol);
    case 't': return q14(symbol);
    case 'u': return q14(symbol);
    case 'v': return q14(symbol);
    case 'w': return q14(symbol);
    case 'x': return q14(symbol);
    case 'y': return q14(symbol);
    case 'z': return q14(symbol);
    case '$': return ACEITA;
    default : return REJEITA;
  }
}

Arquivo makefile

##########################################################################
 # Copyright (C) 2009/2018 - 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

Arquivo DeterministicFiniteAutomaton.pas

(*************************************************************************
 * Copyright (C) 2009/2018 - 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;

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 := q0(symbol + 1);
    'b' : q0 := q0(symbol + 1);
    'c' : q0 := q0(symbol + 1);
    'd' : q0 := q0(symbol + 1);
    'e' : q0 := q0(symbol + 1);
    'f' : q0 := q0(symbol + 1);
    'g' : q0 := q0(symbol + 1);
    'h' : q0 := q0(symbol + 1);
    'i' : q0 := q0(symbol + 1);
    'j' : q0 := q1(symbol + 1);
    'k' : q0 := q0(symbol + 1);
    'l' : q0 := q0(symbol + 1);
    'm' : q0 := q0(symbol + 1);
    'n' : q0 := q0(symbol + 1);
    'o' : q0 := q0(symbol + 1);
    'p' : q0 := q0(symbol + 1);
    'q' : q0 := q0(symbol + 1);
    'r' : q0 := q0(symbol + 1);
    's' : q0 := q8(symbol + 1);
    't' : q0 := q0(symbol + 1);
    'u' : q0 := q0(symbol + 1);
    'v' : q0 := q0(symbol + 1);
    'w' : q0 := q0(symbol + 1);
    'x' : q0 := q0(symbol + 1);
    'y' : q0 := q0(symbol + 1);
    'z' : q0 := q0(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
    'a' : q1 := q0(symbol + 1);
    'b' : q1 := q0(symbol + 1);
    'c' : q1 := q0(symbol + 1);
    'd' : q1 := q0(symbol + 1);
    'e' : q1 := q0(symbol + 1);
    'f' : q1 := q0(symbol + 1);
    'g' : q1 := q0(symbol + 1);
    'h' : q1 := q0(symbol + 1);
    'i' : q1 := q0(symbol + 1);
    'j' : q1 := q1(symbol + 1);
    'k' : q1 := q0(symbol + 1);
    'l' : q1 := q0(symbol + 1);
    'm' : q1 := q0(symbol + 1);
    'n' : q1 := q0(symbol + 1);
    'o' : q1 := q2(symbol + 1);
    'p' : q1 := q0(symbol + 1);
    'q' : q1 := q0(symbol + 1);
    'r' : q1 := q0(symbol + 1);
    's' : q1 := q8(symbol + 1);
    't' : q1 := q0(symbol + 1);
    'u' : q1 := q0(symbol + 1);
    'v' : q1 := q0(symbol + 1);
    'w' : q1 := q0(symbol + 1);
    'x' : q1 := q0(symbol + 1);
    'y' : q1 := q0(symbol + 1);
    'z' : q1 := q0(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
    'a' : q2 := q0(symbol + 1);
    'b' : q2 := q0(symbol + 1);
    'c' : q2 := q0(symbol + 1);
    'd' : q2 := q0(symbol + 1);
    'e' : q2 := q0(symbol + 1);
    'f' : q2 := q0(symbol + 1);
    'g' : q2 := q3(symbol + 1);
    'h' : q2 := q0(symbol + 1);
    'i' : q2 := q0(symbol + 1);
    'j' : q2 := q1(symbol + 1);
    'k' : q2 := q0(symbol + 1);
    'l' : q2 := q0(symbol + 1);
    'm' : q2 := q0(symbol + 1);
    'n' : q2 := q0(symbol + 1);
    'o' : q2 := q0(symbol + 1);
    'p' : q2 := q0(symbol + 1);
    'q' : q2 := q0(symbol + 1);
    'r' : q2 := q0(symbol + 1);
    's' : q2 := q8(symbol + 1);
    't' : q2 := q0(symbol + 1);
    'u' : q2 := q0(symbol + 1);
    'v' : q2 := q0(symbol + 1);
    'w' : q2 := q0(symbol + 1);
    'x' : q2 := q0(symbol + 1);
    'y' : q2 := q0(symbol + 1);
    'z' : q2 := q0(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
    'a' : q3 := q4(symbol + 1);
    'b' : q3 := q0(symbol + 1);
    'c' : q3 := q0(symbol + 1);
    'd' : q3 := q0(symbol + 1);
    'e' : q3 := q0(symbol + 1);
    'f' : q3 := q0(symbol + 1);
    'g' : q3 := q0(symbol + 1);
    'h' : q3 := q0(symbol + 1);
    'i' : q3 := q0(symbol + 1);
    'j' : q3 := q1(symbol + 1);
    'k' : q3 := q0(symbol + 1);
    'l' : q3 := q0(symbol + 1);
    'm' : q3 := q0(symbol + 1);
    'n' : q3 := q0(symbol + 1);
    'o' : q3 := q14(symbol + 1);
    'p' : q3 := q0(symbol + 1);
    'q' : q3 := q0(symbol + 1);
    'r' : q3 := q0(symbol + 1);
    's' : q3 := q8(symbol + 1);
    't' : q3 := q0(symbol + 1);
    'u' : q3 := q0(symbol + 1);
    'v' : q3 := q0(symbol + 1);
    'w' : q3 := q0(symbol + 1);
    'x' : q3 := q0(symbol + 1);
    'y' : q3 := q0(symbol + 1);
    'z' : q3 := q0(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 := q0(symbol + 1);
    'b' : q4 := q0(symbol + 1);
    'c' : q4 := q0(symbol + 1);
    'd' : q4 := q0(symbol + 1);
    'e' : q4 := q0(symbol + 1);
    'f' : q4 := q0(symbol + 1);
    'g' : q4 := q0(symbol + 1);
    'h' : q4 := q0(symbol + 1);
    'i' : q4 := q0(symbol + 1);
    'j' : q4 := q1(symbol + 1);
    'k' : q4 := q0(symbol + 1);
    'l' : q4 := q0(symbol + 1);
    'm' : q4 := q0(symbol + 1);
    'n' : q4 := q0(symbol + 1);
    'o' : q4 := q0(symbol + 1);
    'p' : q4 := q0(symbol + 1);
    'q' : q4 := q0(symbol + 1);
    'r' : q4 := q0(symbol + 1);
    's' : q4 := q8(symbol + 1);
    't' : q4 := q5(symbol + 1);
    'u' : q4 := q0(symbol + 1);
    'v' : q4 := q0(symbol + 1);
    'w' : q4 := q0(symbol + 1);
    'x' : q4 := q0(symbol + 1);
    'y' : q4 := q0(symbol + 1);
    'z' : q4 := q0(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
    'a' : q5 := q0(symbol + 1);
    'b' : q5 := q0(symbol + 1);
    'c' : q5 := q0(symbol + 1);
    'd' : q5 := q0(symbol + 1);
    'e' : q5 := q0(symbol + 1);
    'f' : q5 := q0(symbol + 1);
    'g' : q5 := q0(symbol + 1);
    'h' : q5 := q0(symbol + 1);
    'i' : q5 := q6(symbol + 1);
    'j' : q5 := q1(symbol + 1);
    'k' : q5 := q0(symbol + 1);
    'l' : q5 := q0(symbol + 1);
    'm' : q5 := q0(symbol + 1);
    'n' : q5 := q0(symbol + 1);
    'o' : q5 := q0(symbol + 1);
    'p' : q5 := q0(symbol + 1);
    'q' : q5 := q0(symbol + 1);
    'r' : q5 := q0(symbol + 1);
    's' : q5 := q8(symbol + 1);
    't' : q5 := q0(symbol + 1);
    'u' : q5 := q0(symbol + 1);
    'v' : q5 := q0(symbol + 1);
    'w' : q5 := q0(symbol + 1);
    'x' : q5 := q0(symbol + 1);
    'y' : q5 := q0(symbol + 1);
    'z' : q5 := q0(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 := q0(symbol + 1);
    'b' : q6 := q0(symbol + 1);
    'c' : q6 := q0(symbol + 1);
    'd' : q6 := q0(symbol + 1);
    'e' : q6 := q0(symbol + 1);
    'f' : q6 := q0(symbol + 1);
    'g' : q6 := q0(symbol + 1);
    'h' : q6 := q0(symbol + 1);
    'i' : q6 := q0(symbol + 1);
    'j' : q6 := q1(symbol + 1);
    'k' : q6 := q0(symbol + 1);
    'l' : q6 := q0(symbol + 1);
    'm' : q6 := q0(symbol + 1);
    'n' : q6 := q7(symbol + 1);
    'o' : q6 := q0(symbol + 1);
    'p' : q6 := q0(symbol + 1);
    'q' : q6 := q0(symbol + 1);
    'r' : q6 := q0(symbol + 1);
    's' : q6 := q8(symbol + 1);
    't' : q6 := q0(symbol + 1);
    'u' : q6 := q0(symbol + 1);
    'v' : q6 := q0(symbol + 1);
    'w' : q6 := q0(symbol + 1);
    'x' : q6 := q0(symbol + 1);
    'y' : q6 := q0(symbol + 1);
    'z' : q6 := q0(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
    'a' : q7 := q14(symbol + 1);
    'b' : q7 := q0(symbol + 1);
    'c' : q7 := q0(symbol + 1);
    'd' : q7 := q0(symbol + 1);
    'e' : q7 := q0(symbol + 1);
    'f' : q7 := q0(symbol + 1);
    'g' : q7 := q0(symbol + 1);
    'h' : q7 := q0(symbol + 1);
    'i' : q7 := q0(symbol + 1);
    'j' : q7 := q1(symbol + 1);
    'k' : q7 := q0(symbol + 1);
    'l' : q7 := q0(symbol + 1);
    'm' : q7 := q0(symbol + 1);
    'n' : q7 := q0(symbol + 1);
    'o' : q7 := q0(symbol + 1);
    'p' : q7 := q0(symbol + 1);
    'q' : q7 := q0(symbol + 1);
    'r' : q7 := q0(symbol + 1);
    's' : q7 := q8(symbol + 1);
    't' : q7 := q0(symbol + 1);
    'u' : q7 := q0(symbol + 1);
    'v' : q7 := q0(symbol + 1);
    'w' : q7 := q0(symbol + 1);
    'x' : q7 := q0(symbol + 1);
    'y' : q7 := q0(symbol + 1);
    'z' : q7 := q0(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
    'a' : q8 := q0(symbol + 1);
    'b' : q8 := q0(symbol + 1);
    'c' : q8 := q0(symbol + 1);
    'd' : q8 := q0(symbol + 1);
    'e' : q8 := q9(symbol + 1);
    'f' : q8 := q0(symbol + 1);
    'g' : q8 := q0(symbol + 1);
    'h' : q8 := q0(symbol + 1);
    'i' : q8 := q0(symbol + 1);
    'j' : q8 := q1(symbol + 1);
    'k' : q8 := q0(symbol + 1);
    'l' : q8 := q0(symbol + 1);
    'm' : q8 := q0(symbol + 1);
    'n' : q8 := q0(symbol + 1);
    'o' : q8 := q0(symbol + 1);
    'p' : q8 := q0(symbol + 1);
    'q' : q8 := q0(symbol + 1);
    'r' : q8 := q0(symbol + 1);
    's' : q8 := q8(symbol + 1);
    't' : q8 := q0(symbol + 1);
    'u' : q8 := q0(symbol + 1);
    'v' : q8 := q0(symbol + 1);
    'w' : q8 := q0(symbol + 1);
    'x' : q8 := q0(symbol + 1);
    'y' : q8 := q0(symbol + 1);
    'z' : q8 := q0(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 := q0(symbol + 1);
    'b' : q9 := q0(symbol + 1);
    'c' : q9 := q0(symbol + 1);
    'd' : q9 := q0(symbol + 1);
    'e' : q9 := q0(symbol + 1);
    'f' : q9 := q0(symbol + 1);
    'g' : q9 := q0(symbol + 1);
    'h' : q9 := q0(symbol + 1);
    'i' : q9 := q0(symbol + 1);
    'j' : q9 := q1(symbol + 1);
    'k' : q9 := q0(symbol + 1);
    'l' : q9 := q0(symbol + 1);
    'm' : q9 := q0(symbol + 1);
    'n' : q9 := q10(symbol + 1);
    'o' : q9 := q0(symbol + 1);
    'p' : q9 := q0(symbol + 1);
    'q' : q9 := q0(symbol + 1);
    'r' : q9 := q0(symbol + 1);
    's' : q9 := q8(symbol + 1);
    't' : q9 := q0(symbol + 1);
    'u' : q9 := q0(symbol + 1);
    'v' : q9 := q0(symbol + 1);
    'w' : q9 := q0(symbol + 1);
    'x' : q9 := q14(symbol + 1);
    'y' : q9 := q0(symbol + 1);
    'z' : q9 := q0(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 := q0(symbol + 1);
    'b' : q10 := q0(symbol + 1);
    'c' : q10 := q0(symbol + 1);
    'd' : q10 := q0(symbol + 1);
    'e' : q10 := q0(symbol + 1);
    'f' : q10 := q0(symbol + 1);
    'g' : q10 := q0(symbol + 1);
    'h' : q10 := q0(symbol + 1);
    'i' : q10 := q0(symbol + 1);
    'j' : q10 := q1(symbol + 1);
    'k' : q10 := q0(symbol + 1);
    'l' : q10 := q0(symbol + 1);
    'm' : q10 := q0(symbol + 1);
    'n' : q10 := q0(symbol + 1);
    'o' : q10 := q0(symbol + 1);
    'p' : q10 := q0(symbol + 1);
    'q' : q10 := q0(symbol + 1);
    'r' : q10 := q0(symbol + 1);
    's' : q10 := q8(symbol + 1);
    't' : q10 := q0(symbol + 1);
    'u' : q10 := q0(symbol + 1);
    'v' : q10 := q0(symbol + 1);
    'w' : q10 := q0(symbol + 1);
    'x' : q10 := q0(symbol + 1);
    'y' : q10 := q0(symbol + 1);
    'z' : q10 := q0(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 := q0(symbol + 1);
    'b' : q11 := q0(symbol + 1);
    'c' : q11 := q0(symbol + 1);
    'd' : q11 := q0(symbol + 1);
    'e' : q11 := q9(symbol + 1);
    'f' : q11 := q0(symbol + 1);
    'g' : q11 := q0(symbol + 1);
    'h' : q11 := q0(symbol + 1);
    'i' : q11 := q0(symbol + 1);
    'j' : q11 := q1(symbol + 1);
    'k' : q11 := q0(symbol + 1);
    'l' : q11 := q0(symbol + 1);
    'm' : q11 := q0(symbol + 1);
    'n' : q11 := q0(symbol + 1);
    'o' : q11 := q0(symbol + 1);
    'p' : q11 := q0(symbol + 1);
    'q' : q11 := q0(symbol + 1);
    'r' : q11 := q0(symbol + 1);
    's' : q11 := q8(symbol + 1);
    't' : q11 := q0(symbol + 1);
    'u' : q11 := q12(symbol + 1);
    'v' : q11 := q0(symbol + 1);
    'w' : q11 := q0(symbol + 1);
    'x' : q11 := q0(symbol + 1);
    'y' : q11 := q0(symbol + 1);
    'z' : q11 := q0(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 := q13(symbol + 1);
    'b' : q12 := q0(symbol + 1);
    'c' : q12 := q0(symbol + 1);
    'd' : q12 := q0(symbol + 1);
    'e' : q12 := q0(symbol + 1);
    'f' : q12 := q0(symbol + 1);
    'g' : q12 := q0(symbol + 1);
    'h' : q12 := q0(symbol + 1);
    'i' : q12 := q0(symbol + 1);
    'j' : q12 := q1(symbol + 1);
    'k' : q12 := q0(symbol + 1);
    'l' : q12 := q0(symbol + 1);
    'm' : q12 := q0(symbol + 1);
    'n' : q12 := q0(symbol + 1);
    'o' : q12 := q0(symbol + 1);
    'p' : q12 := q0(symbol + 1);
    'q' : q12 := q0(symbol + 1);
    'r' : q12 := q0(symbol + 1);
    's' : q12 := q8(symbol + 1);
    't' : q12 := q0(symbol + 1);
    'u' : q12 := q0(symbol + 1);
    'v' : q12 := q0(symbol + 1);
    'w' : q12 := q0(symbol + 1);
    'x' : q12 := q0(symbol + 1);
    'y' : q12 := q0(symbol + 1);
    'z' : q12 := q0(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 := q0(symbol + 1);
    'b' : q13 := q0(symbol + 1);
    'c' : q13 := q0(symbol + 1);
    'd' : q13 := q0(symbol + 1);
    'e' : q13 := q0(symbol + 1);
    'f' : q13 := q0(symbol + 1);
    'g' : q13 := q0(symbol + 1);
    'h' : q13 := q0(symbol + 1);
    'i' : q13 := q0(symbol + 1);
    'j' : q13 := q1(symbol + 1);
    'k' : q13 := q0(symbol + 1);
    'l' : q13 := q14(symbol + 1);
    'm' : q13 := q0(symbol + 1);
    'n' : q13 := q0(symbol + 1);
    'o' : q13 := q0(symbol + 1);
    'p' : q13 := q0(symbol + 1);
    'q' : q13 := q0(symbol + 1);
    'r' : q13 := q0(symbol + 1);
    's' : q13 := q8(symbol + 1);
    't' : q13 := q0(symbol + 1);
    'u' : q13 := q0(symbol + 1);
    'v' : q13 := q0(symbol + 1);
    'w' : q13 := q0(symbol + 1);
    'x' : q13 := q0(symbol + 1);
    'y' : q13 := q0(symbol + 1);
    'z' : q13 := q0(symbol + 1);
    else  q13 := REJEITA;
  end;
end;

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

  case sentence[symbol] of
    'a' : q14 := q14(symbol + 1);
    'b' : q14 := q14(symbol + 1);
    'c' : q14 := q14(symbol + 1);
    'd' : q14 := q14(symbol + 1);
    'e' : q14 := q14(symbol + 1);
    'f' : q14 := q14(symbol + 1);
    'g' : q14 := q14(symbol + 1);
    'h' : q14 := q14(symbol + 1);
    'i' : q14 := q14(symbol + 1);
    'j' : q14 := q14(symbol + 1);
    'k' : q14 := q14(symbol + 1);
    'l' : q14 := q14(symbol + 1);
    'm' : q14 := q14(symbol + 1);
    'n' : q14 := q14(symbol + 1);
    'o' : q14 := q14(symbol + 1);
    'p' : q14 := q14(symbol + 1);
    'q' : q14 := q14(symbol + 1);
    'r' : q14 := q14(symbol + 1);
    's' : q14 := q14(symbol + 1);
    't' : q14 := q14(symbol + 1);
    'u' : q14 := q14(symbol + 1);
    'v' : q14 := q14(symbol + 1);
    'w' : q14 := q14(symbol + 1);
    'x' : q14 := q14(symbol + 1);
    'y' : q14 := q14(symbol + 1);
    'z' : q14 := q14(symbol + 1);
    '$' : q14 := ACEITA;
    else  q14 := 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.