¿Puede un FSA contar?

11

Esta puede ser una pregunta tonta. Parece claro que una FSA, dado que es finita, solo puede contar el número de símbolos en su cadena de entrada hasta un número limitado por el número de sus estados. Pero ahora supongamos que equipamos a la FSA con capacidades de salida (por ejemplo, impresión). Entonces sería muy fácil construir una máquina capaz de imprimir un símbolo por cada símbolo que lea. ¿Eso contaría como contar? ¿Si no, porque no?

En cambio, en términos de FST: supongo que no es posible construir un FST capaz de mapear una cadena de una longitud arbitraria a una representación binaria (es decir, un número en el sistema de numeración de base 2) de su longitud. Pero, por supuesto, es trivial construir un FST capaz de asignar una cadena de longitud arbitraria a una cadena de dichos ceros (o unos) de la misma longitud. Pero eso podría contar como contar, no podría, porque lo que está haciendo el FST es construir una representación de la longitud de su entrada. Una representación algo extraña, pero todavía una representación, ¿no es así?

Torbjörn
fuente
1
Entonces, realmente estás haciendo la pregunta "¿qué está contando?" Eso no me parece ciencia de la computación. Sería informática si su pregunta fuera "para esta definición de conteo, ¿puede un FSA contar?".
Sasho Nikolov

Respuestas:

8

Esta pregunta es un poco vaga, así que aquí hay una respuesta vaga: traducir unario a unario no es exactamente contar, ya que la máquina en realidad no "sabe" cuál era el tamaño de la entrada "al final".

Te das cuenta de esto, por supuesto, por eso cuestionas el hecho de que realmente está contando.

Sin embargo, la traducción de unario a binario parece una operación mucho más avanzada, porque no solo implica contar, sino también aritmética.

Entonces, tal vez la noción más precisa a tener en cuenta, en lugar de contar, es comparar . Es decir, dado dos números (en unario) y , determinar si .1 m1n1mn=m

La capacidad de hacer esta comparación es lo que da lugar al famoso lenguaje no regular . Y la incapacidad de un NFA para contar es lo que hace que este lenguaje no sea regular.{anbn:n0}

Curiosamente, este lenguaje es un CFL. Y, de hecho, el modelo de autómata correspondiente (PDA) tiene la capacidad de hacer una comparación limitada.

Cuando habla de comparar, los transductores ya no le dan potencia adicional, por lo que la pregunta se resuelve en ese sentido.

Una nota adicional: completamente informal, la capacidad de comparar dos números a menudo se puede utilizar para simular una máquina Minsky de 2 contadores , que son equivalentes a TM.

Shaull
fuente
4

No. Los autómatas de estado finito no cuentan. Pueden hacer cosas que parecen, pero no pueden contar. Incluso pueden hacer pequeños cálculos (cableados) (como determinar si un número binario es divisible por tres ), pero eso no cuenta.

Una pequeña historia Estás en una gran plaza rectangular en una ciudad famosa. Los lugareños te dicen que el cuadrado es en realidad cuadrado. Si puede contar, compruebe si los números horizontales y verticales de las fichas coinciden contando las fichas a lo largo de los lados del cuadrado. Si no puede contar, aún puede verificar el reclamo: comience en una esquina y camine en diagonal. Si llega exactamente a la esquina opuesta, tiene un cuadrado.

En su ejemplo las pruebas de la FSA si una cadena tiene un número igual de 's y ' s por medio del conteo estos números a dos cintas de salida diferentes. Otro dispositivo tiene que estar haciendo la comparación final, a menos que tenga un truco para manejar las letras y en pares y cruces uno contra el otro. Como en la plaza.b a babab

Ahora un modelo más formal para comparar. De acuerdo con el Teorema de Chomsky – Schützenberger, cada lenguaje sin contexto es un inverso de una transducción de estado finito del lenguaje Dyck en dos pares de paréntesis (no se dice así) en wikipedia, pero tienes que creerme). Ahora el transductor de estado finito puede "aceptar" su lenguaje libre de contexto siguiente manera (para cada idioma su propio transductor). En la entrada transforma la cadena en la serie (adivinada) de pops y empujones del pda para , luego prueba si el resultado es un comportamiento pushdown, es decir, el resultado es una cadena enT D 2 L = T - 1 ( D 2 ) T L T L D 2 w T - 1 ( D 2 ) T ( w ) D 2LTD2L=T1(D2)TLTLD2 . (Se omiten los detalles técnicos, pero esto es como lo afirma el Teorema de Ch-Sch: uno tiene iff )wT1(D2)T(w)D2

Mi punto aquí es que el transductor realiza algunos "cálculos", pero se oculta mucha potencia en la prueba con . Del mismo modo, su ejemplo, donde dos letras se ordenan en dos cintas. D2

Hendrik Jan
fuente
Puedo construir un DFA que cuente entre y (Para fijo ) o incluso en . Eso es más de lo que cualquier computadora humana o real maneja. ¿A qué llamarías contar? 2 n ! n N02n!nN
Raphael
@Raphael. Por supuesto. Y fácilmente números más grandes que eso. Deje de enseñar que los lenguajes libres de contexto son más poderosos que los lenguajes normales: son los mismos (al menos para cadenas de longitud como máximo ). Solo bromeaba. Hacer referencia a lenguajes informáticos reales como ese hace que todo sea un estado finito, ¿no? ¡Los autómatas de estado finito no cuentan! Solo distinguen un número finito de estados, aunque ese número puede ser muy grande. 2n!
Hendrik ene
Pero de la forma en que generalmente se presentan las FSA, solo se les "permite" decir "sí" (aceptado) o "no" (no aceptado). Ante esto, nadie podría construir una FSA que cuente. Si le permitimos informar (por ejemplo, imprimir) el (número del) estado en el que se encuentra cuando termina, entonces puede contar, pero solo hasta un límite dado por el número de estados. Pero si DO permitimos que se imprima, entonces es trivial construir un FSA de estado único que imprima (digamos) 1 cada vez que lee un símbolo de la cadena de entrada, informando así el recuento en la representación de conteo. ¿Qué tiene de malo esta idea?
Torbjörn
Y si nos olvidamos de los informes / impresiones, y pensamos en términos de representaciones internas, una FSA puede contar los símbolos en una cadena, pero no en una larga arbitraria. La FSA de un solo estado, por supuesto, no puede contar en absoluto.
Torbjörn
Hendrik, creo que estamos "debatiendo" una cuestión de semántica: para mí, "contar" puede ser "de uno a diez", lo que puede hacer FA . Cuando se cruzan los autómatas Büchi, por ejemplo, contamos cuántos autómatas (de , fijos) han alcanzado un estado final mientras los otros proceden. Por lo tanto, creo que la afirmación "no se puede contar" es demasiado fuerte. La (única) declaración verdadera es "no puede contar más allá de una constante". k
Raphael
1

@Shaull: ¡Gracias por tu respuesta! Soy nuevo en StackExchange y no sé cómo comentar una respuesta, por lo que elijo escribir una respuesta, con la esperanza de que me perdonen.

Hmm, me parece que un pastor que cuenta sus ovejas escribiendo una marca en un trozo de papel por cada oveja que ve, o un prisionero que cuenta los días que ha estado en la cárcel escribiendo marcas en la pared, están contando. ¿Por qué las marcas n en un trozo de papel o en una pared no cuentan como una representación del número n? ¿No es eso lo que se llama una representación de conteo? AFAICS de ninguna manera es inferior a (digamos) una representación binaria, excepto que usa más espacio.

Supongo que para ti, "saber" significa que tiene una representación interna del recuento al final. Entonces, por supuesto, es obvio que una FSA de FST no puede calcular la longitud de una cadena arbitraria. Pero si no requerimos conocimiento en ese sentido, pero solo exigimos que la FSA o la FST puedan decirle el resultado a un observador externo, entonces me parece que presentar el conteo en un formato de conteo debería estar bien.

Además, si una FSA está equipada con entradas y salidas incrementales, en principio debería poder usar su entorno externo como memoria de lectura / escritura y, por lo tanto, ser tan potente como una máquina Turing. ¿Derecho?

Gracias por mencionar el caso de la comparación. Ahora, parece ser que si levantamos el requisito de una representación interna, y solo requerimos que la máquina pueda presentar el resultado a un observador externo, entonces podríamos construir fácilmente un FSM que podría producir una especie de Presentación gráfica del resultado. Supongamos que el FSM, al leer "aaaaaabbbbbb" escribió

000000
000000

entonces, dado que las barras tienen la misma longitud, el FSM ha aceptado la cadena "aaaaaabbbbbb". Dos barras de la misma longitud significan "sí", diferentes longitudes significan "no".

Supongo que estoy doblando las reglas, pero eso es lo que quiero ya que estoy interesado en los supuestos más o menos implícitos que se están haciendo en el campo de la lingüística matemática.

Torbjörn
fuente
Quizás su "modelo" pueda verse como una FSA con un número finito (igual al tamaño del alfabeto) de contadores de solo escritura más un estado final especial que puede comparar dos (o más) de ellos y aceptarlos o rechazarlos si son iguales o no. Tal " " es más poderoso que un FSA; pero tiene algunos problemas para reconocer cosas como es decir, hacer aritmética. { a n | n  es primo  }FSAWOC{an|n is prime }
Vor
Creo que la diferencia entre los ejemplos que da y la salida FST es que el pastor puede leer las líneas después de que se escriben, mientras que un FSM no puede. Lo mismo vale para comparar.
Shaull
Puede comentar haciendo clic en el enlace "agregar comentario" debajo de cualquier publicación.
Raphael
Cualquier FSA construida para contar una bandada puede contar esa bandada. Ninguna FSA construida puede contar ninguna bandada. La pregunta básica es si el pastor solo sabe contar lo suficiente como para contar al menos su propio rebaño, o si puede usar el rango completo de los números naturales. En mi experiencia, los humanos debemos hacer explícitamente la transición entre las dos capacidades en algún momento de nuestra educación matemática.
reinierpost
1

Los FSM pueden "contar" dentro de un rango finito / número de pasos significados por transiciones de estado. sin embargo, no pueden contar más allá de un número finito de pasos.

En cierto sentido, una máquina similar a la FSA puede contar. una máquina estrechamente relacionada se llama Transductor de estado finito . de hecho, el transductor puede contar en el sentido de entrada y salida "canalizada". un solo transductor puede tomar una secuencia de entrada (digamos en binario) y "transducirla" a una secuencia de salida que se incrementa. entonces uno "encadena" los (idénticos) transductores de conteo por 1, cada uno incrementa su entrada en 1 y la emite. también es como un "algoritmo de transmisión" rudimentario .

vzn
fuente
Más detalles: el transductor puede incrementar el funcionamiento en orden "lsb" a "msb", es decir, "bit de menor sig" a "bit de mayor sig" utilizando una lógica similar al sumador completo EE .
vzn
Parece que los transductores de estado finito no se han estudiado mucho. Hay otra aplicación interesante para la conjetura de collatz en la creación de una máquina que calcula iteraciones. cualquier persona interesada en más teoría / discusión por favor contácteme en el chat o en mi blog .
vzn