Autómatas finitos deterministas (AFD)

Deja un comentario

Hoy haremos un breve repaso a los autómatas finitos deterministas con este video-tutorial en el que explica como crear dicho autómatas finitos deterministas (AFD)

Espero que os sirva de ayuda

Anuncios

Lenguajes formales

Deja un comentario

Hoy vamos a explicar un tema importante sobre los autómatas finitos, ¿que es un lenguajes formal?, ya que aparte de la utilización de los lenguajes formales en los autómatas finitos, también son utilizados en otras ciencias como en las matemáticas, en lógica computacional, y en ciencias de la computacion

En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados.1 2 Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.

Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.

Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial con los lenguajes naturales.

En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante \epsilon \,, e\, o \lambda \,.

Espero que os sirva de ayuda, un saludo!

Autómatas finitos, gramáticas y lenguajes formales

Deja un comentario

Hoy volvemos de nuestras pequeñas vacaciones,  y para ello vamos a mostrar una pequeña imagen con un mapa conceptual que respresenta la mayoría del contenido de nuestro blog.

automatas finitos

automatas finitos

Introducción a JFLAP (herramienta para la visualización de lenguajes formales)

Deja un comentario

JFLAP (Java Formal Language and Automata Package) es una herramienta para la enseñanza y la visualización interactiva de lenguajes formales. Permite crear y operar sobre autómatas (finitos, máquinas de Moore y Mealy, Turing…), gramáticas, expresiones regulares y L-systems. En esta práctica inicial sólo nos vamos a centrar en la parte enfocada a las gramáticas, y según avance el curso, iremos profundizando en los distintos apartados de la aplicación. Aunque algunas secciones no se verán en la asignatura.

Os dejamos un enlace en el que viene un completo tutorial sobre JFLAP, y además también os dejamos la propia aplicación.

Manual JFLAP

Aplicación JFLAP

También podeís ver este video explicativo en el que JFLAP utiliza gramáticas que forman los distintos autómatas.

Un saludo, espero que os sirva de ayuda!!

Lenguajes formales

Deja un comentario

Como ayer, hoy traemos otro video con un pequeño tutorial acerca de los lenguajes formales y sobre expresiones regulares, espero que os sirva de ayuda.

Mañana seguiremos actualizando el blog, un saludo a tod@s!

Autómatas finitos deterministas y no deterministas

2 comentarios

Hoy traemos un pequeño resumen acerca de los autómatas finitos deterministas (AFD) y los autómatas finitos no deterministas (AFND)
Autómata finito determinista (AFD)
Cada estado de un autómata de este tipo tiene una transición por cada símbolo del alfabeto.

AFD.

Autómata finito no determinista (AFND)
Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra es rechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer ningún símbolo. Si un estado tiene transiciones etiquetadas con \epsilon, entonces el AFND puede encontrarse en cualquier de los estados alcanzables por las transiciones \epsilon, directamente o a través de otros estados con transiciones \epsilon. El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura \epsilon de q.

Sin embargo, puede observarse que todos estos tipos de autómatas pueden aceptar los mismos lenguajes. Siempre se puede construir un AFD que acepte el mismo lenguaje que el dado por un AFND.

Autómatas finitos no deterministas

Deja un comentario

Estamos realizando actualizaciones sobre los apuntes e imágenes acerca de los autómatas finitos no deterministas, espero que os sirvan de ayuda

Older Entries