1. DFA: DFA se refiere a un autómata finito determinista. Se dice que un autómata finito (FA) es determinista si corresponde a un símbolo de entrada, hay un solo estado resultante, es decir, solo hay una transición. Un autómata finito determinista es un conjunto de cinco tuplas representadas como, Donde, Q: Un conjunto finito no … Continue reading «Diferencia entre DFA y NFA»
Dada una string que consta de los caracteres a y b , compruebe si la string comienza y termina con el mismo carácter o no. Si es así, escriba ‘Sí’; de lo contrario, escriba ‘No’. Ejemplos: Entrada: str = “abbaaba” Salida: Sí Explicación: La string de entrada dada comienza y termina con el mismo carácter … Continue reading «Programa para construir un DFA para aceptar strings que comienzan y terminan con el mismo carácter»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema: diseñar un PDA no determinista para aceptar el lenguaje L ={w?{a,b}* | w contiene igual no. de a’s y b’s}, es decir, L = {ab, aabb, abba, aababb, bbabaa, baaababb, …….} El número de a y b es el mismo en todas … Continue reading «NPDA para el lenguaje L ={w∈ {a,b}*| w contiene igual no. de a y b}»
Problema: acepte strings que no terminen con la substring «EL». Compruebe si una string dada termina con «el» o no. Las diferentes formas de “the” que se evitan al final de la string son: «THE», «ThE», «THe», «tHE», «thE», «The», «tHe» and «the» No se aceptan todas aquellas strings que terminan con cualquiera de las … Continue reading «DFA para strings que no terminan en «THE»»
Requisito previo: autómatas pushdown , NPDA para aceptar el lenguaje L = {a m b n c (m+n) | m,n ≥ 1} PDA juega un papel muy importante en la tarea de diseño del compilador. Por eso es necesario tener una buena práctica en PDA. Nuestro objetivo es construir una PDA que acepte una string … Continue reading «Construir autómatas pushdown para L = {0n1m2(n+m) | m, n ≥ 0}»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema: diseñar un PDA no determinista para aceptar el lenguaje L = { : i==k o j==l, i>=1, j>=1}, es decir, L = {abcd, aabccd, aaabcccd, abbcdd, aabbccdd, aabbbccddd, ……} En cada string, el número de a va seguido de cualquier número de … Continue reading «NPDA por aceptar el lenguaje L = {aibjckdl | i==k o j==l,i>=1,j>=1}»
Una máquina de Turing estándar es una máquina que al proporcionar una entrada se mueve hacia la izquierda o hacia la derecha y puede sobrescribir el símbolo existente. Una TM estándar se puede describir como una tupla de 7: (Q, X, *, f, q0, B, F) where Q is a finite set of states X … Continue reading «Modificaciones a la máquina de Turing estándar»
Para comprender mejor el problema de la detención, debemos conocer la Decidibilidad , la Indecidibilidad y la máquina de Turing , los problemas de decisión y también una teoría denominada Teoría de la Computabilidad y Teoría de la Complejidad Computacional. Algunos términos importantes: Teoría de la computabilidad: la rama de la teoría de la computación … Continue reading «Problema de detención en la teoría de la computación»
Requisito previo: diseño de autómatas finitos En este artículo, veremos algunos diseños de autómatas finitos deterministas (DFA). Problema-1: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que el segundo símbolo del lado izquierdo siempre es ‘b’. Explicación: El idioma deseado será como: L1 = {ab, aba, abaa, … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 8)»
La expresión regular puede ser cualquier cosa, desde un símbolo terminal, ∅, hasta la unión de dos expresiones regulares (R 1 + R 2 ), su concatenación (R 1 R 2 ) o su cierre R 1 * también. Ejemplos de expresiones regulares: Expresión regular del conjunto de todas las strings de 0 y 1 … Continue reading «DFA de 0 y 1 alternativos»