Preguntas sobre dispositivos matemáticos que leen un flujo de entrada símbolo por símbolo y usan un mapa de transición de estado para producir un flujo de salida, tal vez usando almacenamiento secundario.
Convertir expresiones regulares en NFA (mínimo) que acepten el mismo lenguaje es fácil con algoritmos estándar, por ejemplo, el algoritmo de Thompson . Sin embargo, la otra dirección parece ser más tediosa, y a veces las expresiones resultantes son desordenadas. ¿Qué algoritmos existen para...
Estoy de acuerdo en que una máquina de Turing puede resolver "todos los posibles problemas matemáticos". Pero eso se debe a que es solo una representación de la máquina de un algoritmo: primero haga esto, luego haga eso, finalmente obtenga eso. Quiero decir que cualquier cosa que sea solucionable...
Existen muchos métodos para demostrar que un idioma no es regular , pero ¿qué debo hacer para demostrar que un idioma es regular? Por ejemplo, si me dicen que LLL es regular, ¿cómo puedo probar que la siguiente L′L′L' es regular? L′: = { w ∈ L : u v = w para u ∈ Σ∗∖ L y v ∈...
Consulte el final de esta publicación para obtener algunas aclaraciones sobre las definiciones de los autómatas min-heap. Uno puede imaginarse usando una variedad de estructuras de datos para almacenar información para uso de las máquinas de estado. Por ejemplo, los autómatas push-down almacenan...
En esta respuesta se menciona Un lenguaje normal puede ser reconocido por un autómata finito. Un lenguaje sin contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina Turing completa) . Quería saber sobre la verdad de...
Llamemos a un lenguaje determinista sin contexto si y solo si puede ser aceptado por un autómata determinista de empuje hacia abajo, y no determinista de lo contrario. Llamemos a un lenguaje libre de contexto inherentemente ambiguo si y solo si todas las gramáticas libres de contexto que generan...
En la teoría de los autómatas, todos leemos autómatas como autómatas finitos, desde el principio. Lo que quiero saber es, ¿por qué los autómatas son finitos? Para ser claros, ¿qué hay en un autómata que es finito: el alfabeto, el idioma, las cadenas hechas con expresiones regulares o qué? ¿Y hay...
Al ver que en la Jerarquía de Chomsky, los lenguajes Tipo 3 pueden ser reconocidos por una máquina de estado sin memoria externa (es decir, un autómata finito), el Tipo 2 por una máquina de estado con una sola pila (es decir, un autómata pushdown) y el Tipo 0 una máquina de estados con dos pilas...
En mi clase, un estudiante preguntó si todos los autómatas finitos podían dibujarse sin cruzar bordes (parece que todos mis ejemplos lo hicieron). Por supuesto, la respuesta es negativa, el autómata obvio para el idioma tiene la estructura de K_5 , el gráfico completo en cinco nodos . Yuval ha...
Acabo de completar el primer capítulo de Introducción a la teoría de la computación de Michael Sipser que explica los conceptos básicos de los autómatas finitos. Él define un lenguaje regular como cualquier cosa que pueda ser descrita por un autómata finito. Pero no pude encontrar dónde explica...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
Tengo un conjunto de pares. Cada par tiene la forma (x, y) de modo que x, y pertenecen a enteros del rango [0,n). Entonces, si n es 4, entonces tengo los siguientes pares: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Ya tengo las parejas. Ahora, tengo que construir una combinación usando n/2pares de...
Estoy haciendo una presentación sobre las máquinas Turing y quería dar algunos antecedentes sobre los FSM antes de presentar las máquinas Turing. El problema es que realmente no sé qué es MUY diferente el uno del otro. Esto es lo que sé que es diferente: FSM tiene estados secuenciales...
Esta pregunta se migró de Stack Overflow porque se puede responder en Computer Science Stack Exchange. Migrado hace 7 años . Creé un simple lexer y analizador de expresiones regulares para tomar una expresión regular y generar su árbol de análisis. Crear un autómata de...
¿El siguiente contexto de lenguaje es gratuito? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Como señaló sdcvvc, una palabra en este lenguaje también se puede...
Sabemos que los DFA son equivalentes a los NFA en poder de expresividad; También hay un algoritmo conocido para convertir NFA a DFA (desafortunadamente ahora conozco al inventor de ese algoritmo), que en el peor de los casos nos da estados, si nuestro NFA tenía estados.2S2S2^SSSS Mi pregunta es:...
Un autómata es un modelo abstracto de una computadora digital. Las computadoras digitales son completamente deterministas; su estado en cualquier momento es únicamente predecible a partir de la entrada y el estado inicial. Cuando intentamos modelar sistemas reales, ¿por qué incluir el no...
¿Hay algún lenguaje "natural" que sea indecidible? por "natural" me refiero a un lenguaje definido directamente por las propiedades de las cadenas, y no a través de máquinas y su equivalente. En otras palabras, si las miradas del lenguaje como donde M es una MT, DFA (o regular-exp), PDA (o la...
Dada una gramática G sin contexto, existe un Automatismo N Pushdown no determinista que acepta exactamente el lenguaje que G acepta. (y viceversa) También puede existir un Automatismo determinista pushdown D que acepta exactamente el lenguaje que G acepta también. Depende de la gramática. ¿Por...
En mi curso de teoría de la computación, muchos de nuestros problemas implican el uso de la inducción en la longitud de la cadena de entrada para probar declaraciones sobre autómatas finitos. Entiendo la inducción matemática, sin embargo, cuando las cuerdas entran en juego, me tropiezo de verdad....