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:
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:
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
- 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:
- Ingresar autómata
- Verificar de palabra
- 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
Publicar un comentario