Las propiedades de cierre en lenguajes regulares se definen como ciertas operaciones en lenguaje regular que están garantizadas para producir lenguaje regular. El cierre se refiere a alguna operación en un idioma, que da como resultado un nuevo idioma que es del mismo «tipo» que el que se operó originalmente, es decir, regular. Los lenguajes … Continue reading «Propiedades de cierre de lenguajes regulares»
Enumerable recursivo (RE) o Tipo -0 Idioma Los lenguajes RE o lenguajes de tipo 0 son generados por gramáticas de tipo 0. La máquina de Turing puede aceptar o reconocer un idioma RE, lo que significa que entrará en el estado final para las strings de idioma y puede o no entrar en el estado … Continue reading «Lenguajes recursivos y recursivos enumerables en TOC»
Prerrequisito – Máquina de Turing El lenguaje L = {ww | w ∈ {0, 1}} dice que cada string de 0 y 1 que va seguida de sí misma cae dentro de este lenguaje. La lógica para resolver este problema se puede dividir en 2 partes: Hallar el punto medio de la cuerda Después de … Continue reading «Construya una máquina de Turing para el lenguaje L = {ww | w ∈ {0,1}}»
Un autómata es una máquina que tiene un número finito de estados. Cualquier dos autómatas se dice que es equivalente si ambos aceptan exactamente el mismo conjunto de strings de entrada. Dos autómatas son equivalentes si cumplen las siguientes condiciones: 1. Los estados inicial y final de ambos autómatas deben ser iguales. 2. Cada par de … Continue reading «Equivalencia de FSA (autómatas de estado finito)»
Requisito previo: NP-Completitud Aplicaciones del mundo real de la prueba constructiva P=NP: La clase de problemas polinómicos, también conocidos como P, se pueden resolver en tiempo polinomial. Sin embargo, la otra clase de problemas no se pueden resolver en tiempo polinomial, pero la solución se puede verificar con bastante rapidez. Estos son conocidos como problemas … Continue reading «Aplicaciones del mundo real de una prueba constructiva P=NP»
BNF significa notación Backus Naur Form . Es un método formal para describir la sintaxis del lenguaje de programación que se entiende como Backus Naur Formas introducido por John Bakus y Peter Naur en 1960. BNF y CFG (Gramática libre de contexto) eran casi idénticos. BNF puede ser un metalenguaje (un idioma que no puede … Continue reading «Notación BNF en el diseño del compilador»
Requisito previo: máquina de Turing Problema: Dibuja una máquina de turing que compare dos números. Uso del formato unario para representar el número. Por ejemplo, 4 está representado por 4 = 1 1 1 1 or 0 0 0 0 Usemos uno para la representación. Ejemplo: Acercarse: Comparar dos números comparando el número de ‘1’. … Continue reading «Máquina de Turing como comparador – Part 1»
Que-1: Dibuje un autómata finito determinista y no determinista que comience con 01 o termine con 01 de una string que contenga 0, 1, por ejemplo, 01010100 pero no 000111010. Explicación: dibuje un DFA y NFA del mismo idioma cuyas strings solo lleguen al estado final que contenga 01 al principio o al final. Si … Continue reading «Problemas de práctica en autómatas finitos | conjunto 2»
L = {un norte segundo metro un ( n +m) | n,m≥1} representa un tipo de lenguaje en el que usamos solo 2 caracteres, es decir, a y b. La primera parte del lenguaje puede ser cualquier número de «a» (al menos 1). La segunda parte puede ser cualquier número de “b” (al menos 1). … Continue reading «Construya una máquina de Turing para L = {an bm a(n+m) | n,m≥1}»
Requisito previo: diseñar un autómata finito Supongamos que tenemos un DFA que está definido por ( Q, , , q0, F ) y acepta el lenguaje L 1 . Entonces, el DFA que acepta el lenguaje L 2 donde L 2 = ̅L 1 ‘, se definirá como sigue: ( Q, , , q0, Q-F … Continue reading «Proceso de complementación en DFA – Part 1»