Requisitos previos: jerarquía de Chomsky Gramática tipo 3/gramática regular: La gramática regular genera lenguaje regular. Tienen un solo no terminal en el lado izquierdo y un lado derecho que consta de un solo terminal o un solo terminal seguido de un no terminal. Las producciones deben estar en la forma: A ⇢ xB A ⇢ … Continue reading «Gramática regular (Modelo de gramáticas regulares)»
Prerrequisitos: Autómatas finitos Dada una string str que consta de los caracteres a , b y c , verifique si el número de ocurrencias de cualquier carácter en la string es un múltiplo de 3 o no. Ejemplos: Entrada: str = bc Salida: ACEPTADO Explicación: La string consta de 0 a y 3 * 0 … Continue reading «NFA para aceptar strings que tienen al menos un carácter que ocurre en un múltiplo de 3»
Prerrequisito: Introducción a los autómatas finitos En este artículo, veremos algunos diseños de autómatas finitos no deterministas (NFA). Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del lenguaje comienza con ‘a’. Explicación: El idioma deseado será como: L1 = {ab, abba, abaa, ………..} … Continue reading «Diseño de autómatas finitos no deterministas (Conjunto 1)»
Dada una string S que representa un número entero, la tarea es verificar si la string S dada representa un número entero sin signo o no mediante la construcción del DFA . Si la string dada representa un entero sin signo, imprima «Entero sin signo» . De lo contrario, imprima «No es un entero sin … Continue reading «Programa para construir un DFA para verificar si un entero dado no tiene signo o no»
Requisito previo – Diseño de autómatas finitos Inversión: Definimos el lenguaje invertido como el lenguaje , donde Pasos para la reversión: Dibuja los estados tal como son. Agregar un nuevo estado de aceptación único Hacer que el estado de aceptación sea el estado inicial y el estado inicial el estado de aceptación Invertir la función … Continue reading «Inversión de autómatas finitos deterministas»
Requisito previo: autómatas pushdown Problema: Construir autómatas Pushdown para L = {0 (n+m) 1 m 2 n | metro, norte ≥ 0} PDA similares- Esta PDA parece ser similar a la PDA de S2 = {0 m 1 (n+m) 2 n } pero la producción es diferente. S2 producirá una salida que no tiene 1 … Continue reading «Construir autómatas pushdown para L = {0(n+m)1m2n | metro, norte ≥ 0}»
Prerrequisito: Diseño de autómatas finitos , Diseño de autómatas finitos deterministas (Conjunto 2) En este artículo, veremos algunos diseños de Autómatas finitos deterministas (DFA). Problema 1: construcción de un conjunto mínimo de strings de aceptación de DFA sobre {a, b} donde cada string contiene ‘a’ como substring. Explicación: El idioma deseado será como: L1 = … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 3) – Part 1»
El teorema de Myhill Nerode es un resultado fundamental de la teoría de los lenguajes. Esta teoría fue probada por John Myhill y Anil Nerode en 1958. Se usa para probar si un lenguaje L es regular o no y también se usa para minimizar estados en DFA (Deterministic Finite Automata). Para comprender este teorema, … Continue reading «Teoremas básicos en TOC (Teorema de Myhill Nerode)»
Requisito previo: máquina de Turing Un número se representa en formato binario en diferentes autómatas finitos. Por ejemplo, 5 se representa como 101. Sin embargo, en el caso de la suma utilizando una máquina de Turing, se sigue el formato unario. En formato unario, un número se representa ya sea por ceros o por unos. … Continue reading «Máquina de Turing para la adición»
La máquina de Turing fue inventada por Alan Turing en 1936 y se utiliza para aceptar lenguajes enumerables recursivos (generados por gramática de tipo 0). Una máquina de turing consta de una cinta de longitud infinita en la que se pueden realizar operaciones de lectura y escritura. La cinta consta de celdas infinitas en las … Continue reading «Máquina de Turing en TOC»