Desenvolva um autômato finito determinístico sobre o alfabeto Σ = {i, j, k} que reconheça a linguagem L = {w | w possui kij ou kjk como prefixo, jki ou kji como subpalavra e iij ou jij como sufixo}.
M = ({i, j, k}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12}, δ, q0, {q12})
δ | i | j | k |
---|---|---|---|
q0 | - | - | q1 |
q1 | q2 | q3 | - |
q2 | - | q5 | - |
q3 | - | - | q6 |
q4 | q4 | q5 | q7 |
q5 | q4 | q5 | q6 |
q6 | q10 | q8 | q7 |
q7 | q4 | q8 | q7 |
q8 | q11 | q5 | q6 |
q9 | q10 | q10 | q9 |
q10 | q11 | q10 | q9 |
q11 | q11 | q12 | q9 |
q12 | q11 | q10 | q9 |
/*************************************************************************
* 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.exercicio144;
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.exercicio144;
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('k', 1);
states.put(0, q0);
State q1 = new State(false);
q1.addTransition('i', 2);
q1.addTransition('j', 3);
states.put(1, q1);
State q2 = new State(false);
q2.addTransition('j', 5);
states.put(2, q2);
State q3 = new State(false);
q3.addTransition('k', 6);
states.put(3, q3);
State q4 = new State(false);
q4.addTransition('i', 4);
q4.addTransition('j', 5);
q4.addTransition('k', 7);
states.put(4, q4);
State q5 = new State(false);
q5.addTransition('i', 4);
q5.addTransition('j', 5);
q5.addTransition('k', 6);
states.put(5, q5);
State q6 = new State(false);
q6.addTransition('i', 10);
q6.addTransition('j', 8);
q6.addTransition('k', 7);
states.put(6, q6);
State q7 = new State(false);
q7.addTransition('i', 4);
q7.addTransition('j', 8);
q7.addTransition('k', 7);
states.put(7, q7);
State q8 = new State(false);
q8.addTransition('i', 11);
q8.addTransition('j', 5);
q8.addTransition('k', 6);
states.put(8, q8);
State q9 = new State(false);
q9.addTransition('i', 10);
q9.addTransition('j', 10);
q9.addTransition('k', 9);
states.put(9, q9);
State q10 = new State(false);
q10.addTransition('i', 11);
q10.addTransition('j', 10);
q10.addTransition('k', 9);
states.put(10, q10);
State q11 = new State(false);
q11.addTransition('i', 11);
q11.addTransition('j', 12);
q11.addTransition('k', 9);
states.put(11, q11);
State q12 = new State(true);
q12.addTransition('i', 11);
q12.addTransition('j', 10);
q12.addTransition('k', 9);
q12.addTransition('$', 12);
states.put(12, q12);
}
/**
* 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.exercicio144;
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('k', 1);
states->insert(std::pair<int, State*>(0, q0));
State* q1 = new State(false);
q1->addTransition('i', 2);
q1->addTransition('j', 3);
states->insert(std::pair<int, State*>(1, q1));
State* q2 = new State(false);
q2->addTransition('j', 5);
states->insert(std::pair<int, State*>(2, q2));
State* q3 = new State(false);
q3->addTransition('k', 6);
states->insert(std::pair<int, State*>(3, q3));
State* q4 = new State(false);
q4->addTransition('i', 4);
q4->addTransition('j', 5);
q4->addTransition('k', 7);
states->insert(std::pair<int, State*>(4, q4));
State* q5 = new State(false);
q5->addTransition('i', 4);
q5->addTransition('j', 5);
q5->addTransition('k', 6);
states->insert(std::pair<int, State*>(5, q5));
State* q6 = new State(false);
q6->addTransition('i', 10);
q6->addTransition('j', 8);
q6->addTransition('k', 7);
states->insert(std::pair<int, State*>(6, q6));
State* q7 = new State(false);
q7->addTransition('i', 4);
q7->addTransition('j', 8);
q7->addTransition('k', 7);
states->insert(std::pair<int, State*>(7, q7));
State* q8 = new State(false);
q8->addTransition('i', 11);
q8->addTransition('j', 5);
q8->addTransition('k', 6);
states->insert(std::pair<int, State*>(8, q8));
State* q9 = new State(false);
q9->addTransition('i', 10);
q9->addTransition('j', 10);
q9->addTransition('k', 9);
states->insert(std::pair<int, State*>(9, q9));
State* q10 = new State(false);
q10->addTransition('i', 11);
q10->addTransition('j', 10);
q10->addTransition('k', 9);
states->insert(std::pair<int, State*>(10, q10));
State* q11 = new State(false);
q11->addTransition('i', 11);
q11->addTransition('j', 12);
q11->addTransition('k', 9);
states->insert(std::pair<int, State*>(11, q11));
State* q12 = new State(true);
q12->addTransition('i', 11);
q12->addTransition('j', 10);
q12->addTransition('k', 9);
q12->addTransition('$', 12);
states->insert(std::pair<int, State*>(12, q12));
}
/**
* 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);
/**
* 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 'k': return q1(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 'i': return q2(symbol);
case 'j': return q3(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 'j': return q5(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 'k': return q6(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 'i': return q4(symbol);
case 'j': return q5(symbol);
case 'k': return q7(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 'i': return q4(symbol);
case 'j': return q5(symbol);
case 'k': 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 'i': return q10(symbol);
case 'j': return q8(symbol);
case 'k': return q7(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 'i': return q4(symbol);
case 'j': return q8(symbol);
case 'k': return q7(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 'i': return q11(symbol);
case 'j': return q5(symbol);
case 'k': return q6(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 'i': return q10(symbol);
case 'j': return q10(symbol);
case 'k': return q9(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 'i': return q11(symbol);
case 'j': return q10(symbol);
case 'k': return q9(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 'i': return q11(symbol);
case 'j': return q12(symbol);
case 'k': return q9(symbol);
default : return REJEITA;
}
}
/**
* Estado q12 (final)
*
* @param symbol simbolo corrente
* @return ACEITA ou REJEITA
*/
int q12(int symbol)
{
console(12, symbol);
switch(sentence[symbol++])
{
case 'i': return q11(symbol);
case 'j': return q10(symbol);
case 'k': return q9(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;
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
'k' : q0 := q1(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
'i' : q1 := q2(symbol + 1);
'j' : q1 := q3(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
'j' : q2 := q5(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
'k' : q3 := q6(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
'i' : q4 := q4(symbol + 1);
'j' : q4 := q5(symbol + 1);
'k' : q4 := q7(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
'i' : q5 := q4(symbol + 1);
'j' : q5 := q5(symbol + 1);
'k' : 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
'i' : q6 := q10(symbol + 1);
'j' : q6 := q8(symbol + 1);
'k' : q6 := q7(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
'i' : q7 := q4(symbol + 1);
'j' : q7 := q8(symbol + 1);
'k' : q7 := q7(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
'i' : q8 := q11(symbol + 1);
'j' : q8 := q5(symbol + 1);
'k' : q8 := q6(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
'i' : q9 := q10(symbol + 1);
'j' : q9 := q10(symbol + 1);
'k' : q9 := q9(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
'i' : q10 := q11(symbol + 1);
'j' : q10 := q10(symbol + 1);
'k' : q10 := q9(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
'i' : q11 := q11(symbol + 1);
'j' : q11 := q12(symbol + 1);
'k' : q11 := q9(symbol + 1);
else q11 := REJEITA;
end;
end;
(**
* Estado q12 (final)
*
* @param symbol simbolo corrente
* @return ACEITA ou REJEITA
*)
function q12(symbol : integer) : boolean;
begin
console(12, symbol);
case sentence[symbol] of
'i' : q12 := q11(symbol + 1);
'j' : q12 := q10(symbol + 1);
'k' : q12 := q9(symbol + 1);
'$' : q12 := ACEITA;
else q12 := 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.