Ir al contenido principal

Autómata Finito Determinista - Código C++

En esta ocasión les traigo la implementación de un AFD en lenguaje C++. Un autómata finito determinista es una quíntupla que denotaremos de manera genérica por M=(Q,Σ,q0,δ,F), donde:
  • Q es un conjunto finito cuyos elementos llamaremos estados. 
  • Σ es un alfabeto que llamamos alfabeto de entrada. 
  • q0∈Q es un estado señalado que llamamos estado inicial. 
  • F es un subconjunto de Q no vacío, cuyos elementos llamamos estados finales. 
  • δ es una aplicación de Q×Σ→Q , que llamamos función de transición. 


Para la implementación se utiliza una matriz de transición convirtiendo los símbolos y letras del alfabeto en indices de la matriz donde los estados son las FILAS y los símbolos son las COLUMNAS, por ejemplo:

Tenemos un alfabeto Σ = {a, b, c}, entonces en la matriz de transición tomara la letra 'a' como indice 0 , letra 'b' indice 1 y letra 'c' indice 2.

Lo mismo seria para las transiciones, pero allí no interesa que letra representa si no cuantos estados tiene y cual es su estado inicial y cuales son sus estados finales. En el programa que implemente solo pedirá eso cantidad de estados y pregunta por el estado inicial y los finales.

El programa esta dividido en menú de 3 opciones:

  1. Ingresar autómata
  2. Verificar de palabra
  3. Salir

Ingresar autómata: Tendremos que ingresar la cantidad de símbolos y la cantidad de estados. luego tendremos que ingresar los símbolos del alfabeto, los estados los genera solo no es necesario ingresarlo. Seguidamente tendremos que ingresar la matriz de transición donde no olvidemos que remplazamos los nombres de los estados por numero que serian los indices.


Allí tenemos un ejemplo, donde s1 tomaría el valor de 0 y s2 el valor de 1y así tendríamos que ingresarlo en el programa cuando pida la matriz.

Seguidamente tenemos que indicar cual es el estado inicial, supongamos que fuese S1entonces tendriamos que ingresar 1 ó 2 si fuese S2 lo mismo seria para los estados finales.

Verificar palabra: Es la parte donde probamos nuestro autómata, tendremos que ingresarla de acuerdo a nuestro alfabeto de símbolos de ingresamos en la parte de "ingresar autómata".


Implemetación

Comentarios

Entradas populares de este blog

Obtener numeros aleatorios en C++ (rand, srand)

Es algo muy frecuente, cuando ya dominas todo eso de pedir y almacenar datos, ahora tu profesor te pedirá que tus programas generen números aleatorios para automatizar el proceso de llenar arreglos y todo eso. Así que lo primero que tenemos que hacer es incluir la librería: #include<stdlib.h> Necesitamos esta libreria para usar la función time() #include<time.h> Luego inicializar los números aleatorios incluyendo esto: srand(time(NULL)); Luego guardar el número aleatorio en alguna parte: num = rand(); Para ajustar el rango de número aleatorios podemos hacer varias cosas. - Número aleatorios entre 0 y 50:   num=rand()%51; - Número aleatorios entre 1 y 100:   num=1+rand()%(101-1); - Número aleatorios entre 250 y 420:   num=250+rand()%(421-250); De forma general es: variable = limite_inferior + rand() % (limite_superior +1 - limite_inferior) ; Así que un programa que muestre 10 números aleatorios entre 1 y 10 quedaría así:

Árboles Binarios de Búsqueda en C++ | Recorrido por niveles (Amplitud)

Hola a todos en esta ocasión compartiré sobre este tema de Arboles Binarios de Búsqueda, como un poco de teoría para su mejor entendimiento seguidamente mostraré la implementación en lenguaje de programación C++. Primero una breve introducción a árboles. ¿Qué es un árbol? Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol esta formado por subárboles resaltando así su naturaleza recursiva . ¿Qué es un árbol binario? Un árbol binario es aquel es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho. ¿Qué es un árbol binario de búsqueda? Un árbol binario de buque da o ABB, es un árbol bi

Listas Enlazadas Simples Lineales en C++

En esta ocasión les compartire este programa que hize sobre listas  enlazadas simples que hace los siguiente: Inserta al inicio, final, en una posicion a especificar(antes o después), reporta la lista, busca elemento, elimina elemento, elimina elementos repetidos(a especificar). Definición: En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento. Implementación: Sigueme en  facebook y dejame un comentario, agradecer no cuesta nada :D!