Categoría: Theory of Computation & Automata

Requisito previo: simplificación de gramáticas libres de contexto Una gramática libre de contexto (CFG) está en la forma normal de Chomsky (CNF) si todas las reglas de producción satisfacen una de las siguientes condiciones: Un no-terminal que genera un terminal (p. ej., X->x) Un no terminal que genera dos no terminales (p. ej., X->YZ) Símbolo … Continue reading «Conversión de la gramática libre de contexto a la forma normal de Chomsky»

Requisito previo: introducción de FA , expresiones regulares, gramática y lenguaje , diseño de FA a partir de expresiones regulares Hay dos métodos para convertir FA en expresión regular: 1. Método de eliminación de estado: Paso 1: si el estado de inicio es un estado de aceptación o tiene transiciones, agregue un nuevo estado de … Continue reading «Generando expresiones regulares desde Finite Automata – Part 1»

Máquinas de Moore:  Las máquinas de Moore son máquinas de estado finito con valor de salida y su salida depende solo del estado actual. Se puede definir como (Q, q0,  ∑,  O, δ, λ) donde: Q es un conjunto finito de estados. q0 es el estado inicial. ∑  es el alfabeto de entrada. O es … Continue reading «Máquinas de Mealy y Moore en TOC – Part 1»

Requisito previo – Máquina de Turing En el idioma dado L = {a i b j c k | yo < j < k; i≥ 1}, cada string de ‘a’, ‘b’ y ‘c’ tiene cierto número de a, luego cierto número de b y luego cierto número de c. La condición es que el recuento … Continue reading «Construya una máquina de Turing para L = {aibjck | yo < j < k; yo ≥ 1}»

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^m [/Tex] | m, n>=1}, es decir, L = { abc, abbc, abbbc, aabbcc, aaabccc, aaaabbbcccc, …… } En cada una de las strings, el número de a … Continue reading «NPDA por aceptar el lenguaje L = {an bm cn | m,n>=1}»