¿Cuál es la regularidad?

Question

Esto es más una cuestión de la informática que uno de programación, pero calculo que este es el mejor lugar de todos los sitios relacionados a preguntar esto.

Cuando descubrí las expresiones regulares y busqué el término asumí que esta propiedad de "regularidad" se refiere al hecho de que el lenguaje de la expresión tiene un patrón estructural definible. Sin embargo, al leer sobre el tema y la teoría detrás de esto aprendí que hay tipos de lenguajes que no son regulares, y sin embargo a partir de la forma en que se definen, está claro que un patrón se puede adaptar a ellos. Uno de tales lenguaje es (a ^ n) (b ^ n). Es evidente que esto es un patrón, y sin embargo, esto no es un lenguaje regular. Así que ahora estoy izquierda preguntaba de qué se trata lenguajes regulares que les hace regular, y no esta lengua?

Answer 1

La etimología del nombre proviene de la década de 1950 que describe el trabajo de Kleene conjuntos regulares mediante su notación matemática creada para tal fin. Ver este .

Answer 2

Intuitivamente explicar la informática es ... complicado. Voy a darle un tiro, pero tenga en cuenta que algunos de esto va a ser "lo suficientemente cerca", pero no de forma teórica rigurosa.

Un lenguaje regular es uno que puede ser decidido por una máquina que es computacional equivalente a una autómatas finitos (DFA / NDFA). A autómatas finitos puede ser pensado como una máquina que opera puramente en los estados, no almacenamiento. Así se puede ver que a ⁿ b ⁿ no puede ser regular, ya que requiere una máquina que puede contar el número de A y B (y por lo tanto debe tener infinita * capacidad de almacenamiento) con el fin de compararlos.

Para la comparación, (abc) ⁿ es regular, porque el número de repeticiones es irrelevante.

Para una más riguroso (y correspondientemente vista más densa) consultar la wikipedia artículo y páginas enlazadas .

_{* El infinito no importa aquí, pero lo menciono para la integridad. Podría ser más fácil pensar en él como almacenamiento "por suerte, siempre lo justo".}

Answer 3

Tal vez el artículo de Wikipedia sobre lenguajes regulares pueden explicar mejor que podamos. Sin embargo, voy a dar un tiro.

Desde un punto de vista teórico, un lenguaje regular (conjunto de cadenas) es uno que puede ser generada mediante un finita autómata de estados. En términos de programador, esto es equivalente a decir que se pueden generar utilizando expresiones regulares . Por lo tanto, todos los lenguajes finitos (conjuntos de cuerdas) son regulares, pero hay algunas lenguas infinitas, tales como ⁿ b ⁿ (el idioma de todas las cadenas de na de seguido de que no pueden ser reconocidos mediante un FSA o expresiones regulares de n b). Existen dispositivos computacionales más potentes (como las computadoras modernas, que se modelan usando Máquinas de Turing), que puede reconocer esos idiomas.

La razón expresiones regulares se utilizan tanto en la programación para la búsqueda de cadenas es que pueden reconocer la gran mayoría de las cadenas que son importantes para nosotros los programadores, y al mismo tiempo se pueden implementar para buscar muy rápidamente usando un autómata de estados finitos.

Answer 4

La palabra regular en regular expression se refiere al concepto matemático de, no el concepto regular de Inglés. Al igual que cómo la palabra prime en matemáticas tienen poca relación con primer carne de vacuno.

Ha heredado por CS (que es una rama de las matemáticas) para referirse a un concepto más específico: http : //en.wikipedia.org/wiki/Regular_language

Answer 5

expresión regular no son muy regular, el nombre es etimológico.