Una media camarilla en un gráfico es un conjunto de n/2 vértices tales que cada vértice comparte una arista con todos los demás vértices, es decir, los k = n/2 vértices del gráfico forman un gráfico completo. Problema – Dado un gráfico G(V,E), el problema es determinar si el gráfico contiene una camarilla de tamaño … Continue reading «Half clique NP Problema completo»
Dada una string binaria str , la tarea es construir un DFA que acepte una string binaria dada si contiene «01» i veces y «1» 2j veces, es decir, Ejemplos: Entrada: str = “011111” Salida: Aceptada Explicación: La string sigue al idioma como: (01) 1 (1) 2*2 Entrada: str = “01111” Salida: No aceptado … Continue reading «Cree un DFA para aceptar una string binaria que contenga «01» i veces y «1» 2j veces»
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 a n b m c l , donde n, m y l son mayores o iguales a 0. Explicación: el … Continue reading «Diseño de autómatas finitos deterministas (Conjunto 7)»
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 Moore a máquina Mealy. Diagrama de transición de estado de una máquina de Moore: – Arriba, la máquina de Moore toma el número binario {0, 1} como entrada y produce el módulo … Continue reading «Conversión de máquina Moore a Mealy (Set 9)»
Diseñe un autómata finito determinista (DFA) para aceptar el lenguaje Para crear DFA para el lenguaje L = {a n b m | n+m=odd} usa matemáticas elementales que dicen: odd + even = odd, and even+odd = odd Ejemplos: Input: a a b b b Output: ACCEPTED // n = 2, m = 3, 2 … Continue reading «DFA para aceptar el idioma L = {an bm | n+m=impar}»
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 , es decir, L = {abc, aabc, aabbcc, abbbccc, aabbbccc …… } El siguiente DFA debe contener: El número de a es igual al número de c. El número de b es independiente … Continue reading «NPDA por aceptar el lenguaje L = {ambncn | m, n ≥ 1}»
Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 3) En el siguiente artículo, veremos algunos diseños de autómatas finitos a partir de la expresión regular dada: Expresión regular 1: Lenguaje regular, L1 = (a+b)(a+b) El lenguaje del RE dado es, {aa, ab, ba, … Continue reading «Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 4) – Part 1»
Requisito previo – Autómatas pushdown , aceptación de autómatas pushdown por estado final El lenguaje L = {0 i 1 j 2 k | i==j o j==k ; i , j , k >= 1} dice que cada string de ‘0’, ‘1’ y ‘2’ tiene cierto número de 0, luego cierto número de 1 y … Continue reading «NPDA para L = {0i1j2k | i==j o j==k ; yo, j, k >= 1}»
Prerrequisito – Máquina de Turing El idioma L = {ww r | victoria; {0, 1}} representa un tipo de idioma en el que usa solo 2 caracteres, es decir, 0 y 1. La primera parte del idioma puede ser cualquier string de 0 y 1. La segunda parte es el reverso de la primera parte. … Continue reading «Construya una máquina de Turing para el lenguaje L = {wwr | w ∈ {0, 1}}»
Se dice que un lenguaje es regular si se puede representar usando un autómata finito o si se puede generar una expresión regular para él. Esta definición nos lleva a la definición general que; Por cada Expresión Regular correspondiente al lenguaje, se puede generar un Autómata Finito. Para ciertas expresiones como :- (a+b), ab, (a+b)* … Continue reading «Teorema de Kleene en TOC | Parte 1 – Part 1»