Requisito previo: autómatas pushdown , NPDA para aceptar el lenguaje L = {a m b (n+m) c m | m, n >= 1} Problema: Construir autómatas pushdown para L = {0 m 1 (n+m) 2 n | m, n ≥ 0} Ejemplo: Input: 011122 Output: Accepted Input: 00000112222 Output: Not Accepted Enfoque utilizado en esta … Continue reading «Construir autómatas pushdown para L = {0m1(n+m)2n | m, n ≥ 0}»
Problemas decidibles Un problema es decidible si podemos construir una máquina de Turing que se detenga en una cantidad finita de tiempo para cada entrada y responda como ‘sí’ o ‘no’. Un problema decidible tiene un algoritmo para determinar la respuesta para una entrada dada. Ejemplos Equivalencia de dos idiomas regulares: dados dos idiomas regulares, … Continue reading «Indecidibilidad y Reducibilidad en TOC»
Requisito previo: autómatas pushdown y lenguajes libres de contexto . Supongamos que tenemos una gramática libre de contexto G con reglas de producción: S->aSb|bSa|SS|ℇ Derivación más a la izquierda (LMD) y árbol de derivación: la derivación más a la izquierda de una string desde el símbolo inicial S se realiza reemplazando el símbolo no terminal … Continue reading «Ambigüedad en gramática libre de contexto y lenguajes libres de contexto»
Requisito previo: autómatas pushdown , aceptación de autómatas pushdown por estado final Problema – Diseñar un PDA no determinista que acepte el lenguaje L = { [Tex]b^{2n} [/Tex]: n>=1} U { [Tex]b^{n} [/Tex]: n>= 1}, es decir, L = {abb, aabbbb, aaabbbbbb, aaaabbbbbbbb, ……} U {ab, aabb, aaabbb, aaaabbbb, ……} En cada string, el número … Continue reading «NPDA por aceptar el lenguaje L = {anb(2n) | n>=1} U {anbn | n>=1}»
Requisito previo : problema de la máquina de Turing : dibuje la máquina de Turing para aceptar un máximo de dos números unarios n1 y n2 dados como B0n1C0n2B. Si dos números son iguales, entonces acepte cualquiera de los dos números. Lógica utilizada: Por cada 0 en el lado izquierdo, reemplácelo con X y busque … Continue reading «Máquina de Turing para aceptar un máximo de dos números»
Dada una string S , la tarea es diseñar un autómata finito determinista (DFA) para aceptar el lenguaje L = C (A + B)+ . Si DFA acepta la string proporcionada, imprima «Sí» . De lo contrario, escriba “No” . Ejemplos: Entrada: S = “CABABABAB” Salida: Sí Explicación: La string dada tiene la forma C(A … Continue reading «Programa para construir DFA para expresiones regulares C( A + B)+»
Requisito previo : problema de introducción de autómatas finitos : diseñe un autómata finito determinista (DFA) para aceptar el lenguaje La expresión regular para el idioma anterior L es, L = (aa)*.b+ Ejemplos: Input: a a b b b Output: ACCEPTED // n = 2 (even) m=3 (>=1) Input: a a a b b b … Continue reading «Programa para construir un DFA que acepte el lenguaje L = {anbm | n módulo 2=0, m≥1}»
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 acepte un conjunto de strings sobre {a, b} en las que {abwa / wε{a, b}*}. Aquí ‘w’ es la substring que contiene alfabetos sobre cualquier número de ‘a’ y ‘b’ que … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 9)»
Requisito previo: Máquinas Mealy y Moore , diferencia entre la máquina Mealy y la máquina Moore En este artículo, veremos una conversión de máquina Moore a Mealy : diagrama de transición de estado de una máquina Moore: arriba, la máquina Moore toma un conjunto de todas las strings sobre {a, b} como entrada y cuenta … Continue reading «Conversión de máquina Moore a Mealy (Set 4)»
El teorema de Ladner en TOC: como probablemente sepa, independientemente de si P = NP es un problema significativo y desconcertante en el campo de la informática. En complejidad computacional, aquellos problemas que pertenecen a NP-problemas pero que no pueden pertenecer a P o NP-completos se conocen como problemas NP-intermedios . Teniendo en cuenta los … Continue reading «Teorema de Ladner en TOC»