Desenvolva um autômato finito determinístico sobre o alfabeto Σ = {1, 2, 3, 4} que reconheça a linguagem L = {w | w possui 1241 ou 2443 ou 4323 como prefixo, 1431 ou 2342 ou 3421 como subpalavra e 1423 ou 2123 ou 2323 como sufixo}.
M = ({1, 2, 3, 4}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19, q20, q21, q22, q23, q24, q25}, δ, q0, {q25})
δ | 1 | 2 | 3 | 4 |
---|---|---|---|---|
q0 | q1 | q4 | - | q7 |
q1 | - | q2 | - | - |
q2 | - | - | - | q3 |
q3 | q11 | - | - | - |
q4 | - | - | - | q5 |
q5 | - | - | - | q6 |
q6 | - | - | q17 | - |
q7 | - | - | q8 | - |
q8 | - | q9 | - | - |
q9 | - | - | q15 | - |
q10 | q11 | q14 | q17 | q10 |
q11 | q11 | q14 | q17 | q12 |
q12 | q11 | q14 | q13 | q10 |
q13 | q21 | q14 | q17 | q18 |
q14 | q11 | q14 | q15 | q10 |
q15 | q11 | q14 | q17 | q16 |
q16 | q11 | q22 | q17 | q10 |
q17 | q11 | q14 | q17 | q18 |
q18 | q11 | q19 | q17 | q10 |
q19 | q23 | q14 | q15 | q10 |
q20 | q21 | q22 | q20 | q20 |
q21 | q21 | q22 | q20 | q23 |
q22 | q23 | q22 | q23 | q20 |
q23 | q21 | q24 | q20 | q20 |
q24 | q23 | q22 | q25 | q20 |
q25 | q21 | q24 | q20 | q20 |
/*************************************************************************
* 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.exercicio225;
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.exercicio225;
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('1', 1);
q0.addTransition('2', 4);
q0.addTransition('4', 7);
states.put(0, q0);
State q1 = new State(false);
q1.addTransition('2', 2);
states.put(1, q1);
State q2 = new State(false);
q2.addTransition('4', 3);
states.put(2, q2);
State q3 = new State(false);
q3.addTransition('1', 11);
states.put(3, q3);
State q4 = new State(false);
q4.addTransition('4', 5);
states.put(4, q4);
State q5 = new State(false);
q5.addTransition('4', 6);
states.put(5, q5);
State q6 = new State(false);
q6.addTransition('3', 17);
states.put(6, q6);
State q7 = new State(false);
q7.addTransition('3', 8);
states.put(7, q7);
State q8 = new State(false);
q8.addTransition('2', 9);
states.put(8, q8);
State q9 = new State(false);
q9.addTransition('3', 15);
states.put(9, q9);
State q10 = new State(false);
q10.addTransition('1', 11);
q10.addTransition('2', 14);
q10.addTransition('3', 17);
q10.addTransition('4', 10);
states.put(10, q10);
State q11 = new State(false);
q11.addTransition('1', 11);
q11.addTransition('2', 14);
q11.addTransition('3', 17);
q11.addTransition('4', 12);
states.put(11, q11);
State q12 = new State(false);
q12.addTransition('1', 11);
q12.addTransition('2', 14);
q12.addTransition('3', 13);
q12.addTransition('4', 10);
states.put(12, q12);
State q13 = new State(false);
q13.addTransition('1', 21);
q13.addTransition('2', 14);
q13.addTransition('3', 17);
q13.addTransition('4', 18);
states.put(13, q13);
State q14 = new State(false);
q14.addTransition('1', 11);
q14.addTransition('2', 14);
q14.addTransition('3', 15);
q14.addTransition('4', 10);
states.put(14, q14);
State q15 = new State(false);
q15.addTransition('1', 11);
q15.addTransition('2', 14);
q15.addTransition('3', 17);
q15.addTransition('4', 16);
states.put(15, q15);
State q16 = new State(false);
q16.addTransition('1', 11);
q16.addTransition('2', 22);
q16.addTransition('3', 17);
q16.addTransition('4', 10);
states.put(16, q16);
State q17 = new State(false);
q17.addTransition('1', 11);
q17.addTransition('2', 14);
q17.addTransition('3', 17);
q17.addTransition('4', 18);
states.put(17, q17);
State q18 = new State(false);
q18.addTransition('1', 11);
q18.addTransition('2', 19);
q18.addTransition('3', 17);
q18.addTransition('4', 10);
states.put(18, q18);
State q19 = new State(false);
q19.addTransition('1', 23);
q19.addTransition('2', 14);
q19.addTransition('3', 15);
q19.addTransition('4', 10);
states.put(19, q19);
State q20 = new State(false);
q20.addTransition('1', 21);
q20.addTransition('2', 22);
q20.addTransition('3', 20);
q20.addTransition('4', 20);
states.put(20, q20);
State q21 = new State(false);
q21.addTransition('1', 21);
q21.addTransition('2', 22);
q21.addTransition('3', 20);
q21.addTransition('4', 23);
states.put(21, q21);
State q22 = new State(false);
q22.addTransition('1', 23);
q22.addTransition('2', 22);
q22.addTransition('3', 23);
q22.addTransition('4', 20);
states.put(22, q22);
State q23 = new State(false);
q23.addTransition('1', 21);
q23.addTransition('2', 24);
q23.addTransition('3', 20);
q23.addTransition('4', 20);
states.put(23, q23);
State q24 = new State(false);
q24.addTransition('1', 23);
q24.addTransition('2', 22);
q24.addTransition('3', 25);
q24.addTransition('4', 20);
states.put(24, q24);
State q25 = new State(true);
q25.addTransition('1', 21);
q25.addTransition('2', 24);
q25.addTransition('3', 20);
q25.addTransition('4', 20);
q25.addTransition('$', 25);
states.put(25, q25);
}
/**
* 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.exercicio225;
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('1', 1);
q0->addTransition('2', 4);
q0->addTransition('4', 7);
states->insert(std::pair<int, State*>(0, q0));
State* q1 = new State(false);
q1->addTransition('2', 2);
states->insert(std::pair<int, State*>(1, q1));
State* q2 = new State(false);
q2->addTransition('4', 3);
states->insert(std::pair<int, State*>(2, q2));
State* q3 = new State(false);
q3->addTransition('1', 11);
states->insert(std::pair<int, State*>(3, q3));
State* q4 = new State(false);
q4->addTransition('4', 5);
states->insert(std::pair<int, State*>(4, q4));
State* q5 = new State(false);
q5->addTransition('4', 6);
states->insert(std::pair<int, State*>(5, q5));
State* q6 = new State(false);
q6->addTransition('3', 17);
states->insert(std::pair<int, State*>(6, q6));
State* q7 = new State(false);
q7->addTransition('3', 8);
states->insert(std::pair<int, State*>(7, q7));
State* q8 = new State(false);
q8->addTransition('2', 9);
states->insert(std::pair<int, State*>(8, q8));
State* q9 = new State(false);
q9->addTransition('3', 15);
states->insert(std::pair<int, State*>(9, q9));
State* q10 = new State(false);
q10->addTransition('1', 11);
q10->addTransition('2', 14);
q10->addTransition('3', 17);
q10->addTransition('4', 10);
states->insert(std::pair<int, State*>(10, q10));
State* q11 = new State(false);
q11->addTransition('1', 11);
q11->addTransition('2', 14);
q11->addTransition('3', 17);
q11->addTransition('4', 12);
states->insert(std::pair<int, State*>(11, q11));
State* q12 = new State(false);
q12->addTransition('1', 11);
q12->addTransition('2', 14);
q12->addTransition('3', 13);
q12->addTransition('4', 10);
states->insert(std::pair<int, State*>(12, q12));
State* q13 = new State(false);
q13->addTransition('1', 21);
q13->addTransition('2', 14);
q13->addTransition('3', 17);
q13->addTransition('4', 18);
states->insert(std::pair<int, State*>(13, q13));
State* q14 = new State(false);
q14->addTransition('1', 11);
q14->addTransition('2', 14);
q14->addTransition('3', 15);
q14->addTransition('4', 10);
states->insert(std::pair<int, State*>(14, q14));
State* q15 = new State(false);
q15->addTransition('1', 11);
q15->addTransition('2', 14);
q15->addTransition('3', 17);
q15->addTransition('4', 16);
states->insert(std::pair<int, State*>(15, q15));
State* q16 = new State(false);
q16->addTransition('1', 11);
q16->addTransition('2', 22);
q16->addTransition('3', 17);
q16->addTransition('4', 10);
states->insert(std::pair<int, State*>(16, q16));
State* q17 = new State(false);
q17->addTransition('1', 11);
q17->addTransition('2', 14);
q17->addTransition('3', 17);
q17->addTransition('4', 18);
states->insert(std::pair<int, State*>(17, q17));
State* q18 = new State(false);
q18->addTransition('1', 11);
q18->addTransition('2', 19);
q18->addTransition('3', 17);
q18->addTransition('4', 10);
states->insert(std::pair<int, State*>(18, q18));
State* q19 = new State(false);
q19->addTransition('1', 23);
q19->addTransition('2', 14);
q19->addTransition('3', 15);
q19->addTransition('4', 10);
states->insert(std::pair<int, State*>(19, q19));
State* q20 = new State(false);
q20->addTransition('1', 21);
q20->addTransition('2', 22);
q20->addTransition('3', 20);
q20->addTransition('4', 20);
states->insert(std::pair<int, State*>(20, q20));
State* q21 = new State(false);
q21->addTransition('1', 21);
q21->addTransition('2', 22);
q21->addTransition('3', 20);
q21->addTransition('4', 23);
states->insert(std::pair<int, State*>(21, q21));
State* q22 = new State(false);
q22->addTransition('1', 23);
q22->addTransition('2', 22);
q22->addTransition('3', 23);
q22->addTransition('4', 20);
states->insert(std::pair<int, State*>(22, q22));
State* q23 = new State(false);
q23->addTransition('1', 21);
q23->addTransition('2', 24);
q23->addTransition('3', 20);
q23->addTransition('4', 20);
states->insert(std::pair<int, State*>(23, q23));
State* q24 = new State(false);
q24->addTransition('1', 23);
q24->addTransition('2', 22);
q24->addTransition('3', 25);
q24->addTransition('4', 20);
states->insert(std::pair<int, State*>(24, q24));
State* q25 = new State(true);
q25->addTransition('1', 21);
q25->addTransition('2', 24);
q25->addTransition('3', 20);
q25->addTransition('4', 20);
q25->addTransition('$', 25);
states->insert(std::pair<int, State*>(25, q25));
}
/**
* 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);
/**
* 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 '1': return q1(symbol);
case '2': return q4(symbol);
case '4': 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 '2': 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 '4': 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 '1': return q11(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 '4': 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 '4': 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 '3': return q17(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 '3': 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 '2': 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 '3': return q15(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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q17(symbol);
case '4': 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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q17(symbol);
case '4': return q12(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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q13(symbol);
case '4': 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 '1': return q21(symbol);
case '2': return q14(symbol);
case '3': return q17(symbol);
case '4': return q18(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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q15(symbol);
case '4': 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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q17(symbol);
case '4': return q16(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 '1': return q11(symbol);
case '2': return q22(symbol);
case '3': return q17(symbol);
case '4': return q10(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 '1': return q11(symbol);
case '2': return q14(symbol);
case '3': return q17(symbol);
case '4': return q18(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 '1': return q11(symbol);
case '2': return q19(symbol);
case '3': return q17(symbol);
case '4': return q10(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 '1': return q23(symbol);
case '2': return q14(symbol);
case '3': return q15(symbol);
case '4': 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 '1': return q21(symbol);
case '2': return q22(symbol);
case '3': return q20(symbol);
case '4': return q20(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 '1': return q21(symbol);
case '2': return q22(symbol);
case '3': return q20(symbol);
case '4': return q23(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 '1': return q23(symbol);
case '2': return q22(symbol);
case '3': return q23(symbol);
case '4': return q20(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 '1': return q21(symbol);
case '2': return q24(symbol);
case '3': return q20(symbol);
case '4': return q20(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 '1': return q23(symbol);
case '2': return q22(symbol);
case '3': return q25(symbol);
case '4': return q20(symbol);
default : return REJEITA;
}
}
/**
* Estado q25 (final)
*
* @param symbol simbolo corrente
* @return ACEITA ou REJEITA
*/
int q25(int symbol)
{
console(25, symbol);
switch(sentence[symbol++])
{
case '1': return q21(symbol);
case '2': return q24(symbol);
case '3': return q20(symbol);
case '4': return q20(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;
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
'1' : q0 := q1(symbol + 1);
'2' : q0 := q4(symbol + 1);
'4' : 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
'2' : 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
'4' : 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
'1' : q3 := q11(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
'4' : 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
'4' : 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
'3' : q6 := q17(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
'3' : 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
'2' : 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
'3' : q9 := q15(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
'1' : q10 := q11(symbol + 1);
'2' : q10 := q14(symbol + 1);
'3' : q10 := q17(symbol + 1);
'4' : 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
'1' : q11 := q11(symbol + 1);
'2' : q11 := q14(symbol + 1);
'3' : q11 := q17(symbol + 1);
'4' : q11 := q12(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
'1' : q12 := q11(symbol + 1);
'2' : q12 := q14(symbol + 1);
'3' : q12 := q13(symbol + 1);
'4' : 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
'1' : q13 := q21(symbol + 1);
'2' : q13 := q14(symbol + 1);
'3' : q13 := q17(symbol + 1);
'4' : q13 := q18(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
'1' : q14 := q11(symbol + 1);
'2' : q14 := q14(symbol + 1);
'3' : q14 := q15(symbol + 1);
'4' : 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
'1' : q15 := q11(symbol + 1);
'2' : q15 := q14(symbol + 1);
'3' : q15 := q17(symbol + 1);
'4' : q15 := q16(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
'1' : q16 := q11(symbol + 1);
'2' : q16 := q22(symbol + 1);
'3' : q16 := q17(symbol + 1);
'4' : q16 := q10(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
'1' : q17 := q11(symbol + 1);
'2' : q17 := q14(symbol + 1);
'3' : q17 := q17(symbol + 1);
'4' : q17 := q18(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
'1' : q18 := q11(symbol + 1);
'2' : q18 := q19(symbol + 1);
'3' : q18 := q17(symbol + 1);
'4' : q18 := q10(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
'1' : q19 := q23(symbol + 1);
'2' : q19 := q14(symbol + 1);
'3' : q19 := q15(symbol + 1);
'4' : 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
'1' : q20 := q21(symbol + 1);
'2' : q20 := q22(symbol + 1);
'3' : q20 := q20(symbol + 1);
'4' : q20 := q20(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
'1' : q21 := q21(symbol + 1);
'2' : q21 := q22(symbol + 1);
'3' : q21 := q20(symbol + 1);
'4' : q21 := q23(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
'1' : q22 := q23(symbol + 1);
'2' : q22 := q22(symbol + 1);
'3' : q22 := q23(symbol + 1);
'4' : q22 := q20(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
'1' : q23 := q21(symbol + 1);
'2' : q23 := q24(symbol + 1);
'3' : q23 := q20(symbol + 1);
'4' : q23 := q20(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
'1' : q24 := q23(symbol + 1);
'2' : q24 := q22(symbol + 1);
'3' : q24 := q25(symbol + 1);
'4' : q24 := q20(symbol + 1);
else q24 := REJEITA;
end;
end;
(**
* Estado q25 (final)
*
* @param symbol simbolo corrente
* @return ACEITA ou REJEITA
*)
function q25(symbol : integer) : boolean;
begin
console(25, symbol);
case sentence[symbol] of
'1' : q25 := q21(symbol + 1);
'2' : q25 := q24(symbol + 1);
'3' : q25 := q20(symbol + 1);
'4' : q25 := q20(symbol + 1);
'$' : q25 := ACEITA;
else q25 := 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.