¿Qué es la regularidad?

Question

Esto es más una pregunta de informática que una de programación, pero creo que este es el mejor lugar de todos los sitios relacionados para preguntar esto.

Cuando descubrí 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 idiomas que no son regulares, y sin embargo, por la forma en que se definen, está claro que un patrón se puede adaptar a ellos. Uno de esos idiomas es (a^n) (b^n). Claramente este es un patrón, y sin embargo, este no es un lenguaje regular. Entonces, ahora me pregunto ¿qué pasa con los idiomas regulares que los hace regulares, y este lenguaje no?

Answer 1

La etimología del nombre proviene del trabajo de 1950 de Kleene que describe conjuntos regulares utilizando su notación matemática creada para tal fin. Ver this.

Answer 2

La palabra regular en regular expression hace referencia al concepto matemático de regular, no del concepto inglés. Al igual que la palabra prime en matemáticas tiene poca relación con prime carne de res.

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 3

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

Answer 4

Quizás el artículo de Wikipedia en regular languages puede explicarlo mejor que nosotros. Sin embargo, voy a darle una oportunidad.

Desde un punto de vista teórico, un lenguaje normal (conjunto de cadenas) es aquel que se puede generar utilizando un finite state automaton. En términos de programador, esto equivale a decir que se puede generar usando regular expressions. Por lo tanto, todos los lenguajes finitos (conjuntos de cadenas) son regulares, pero hay algunos lenguajes infinitos, como ⁿ b ⁿ (el lenguaje de todas las cadenas de na seguidas de n b) que no se pueden reconocer usando una FSA o expresiones regulares. Existen dispositivos computacionales más potentes (como las computadoras modernas, que se modelan utilizando Turing Machines) que pueden reconocer esos idiomas.

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

Answer 5

Explicar intuitivamente la informática es ... complicado. Le daré una oportunidad, pero tenga en cuenta que algo de esto va a ser "lo suficientemente cerca" pero no teóricamente riguroso.

Un lenguaje regular es aquel que puede decidirse por una máquina que es computacionalmente equivalente a un autómata finito (DFA/NDFA). Se puede pensar en un autómata finito como una máquina que opera puramente en estados, sin almacenamiento. Por lo tanto, puede ver que ⁿⁿ no pueden ser regulares ya que requiere una máquina que puede contar el número de aybs (y por lo tanto debe tener capacidad de almacenamiento infinita *) para poder compararlos.

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

Para obtener una vista más rigurosa (y la densidad correspondiente), consulte wikipedia article y las páginas vinculadas.

_{* Lo infinito no importa aquí, pero lo menciono por completo. Podría ser más fácil pensar en el almacenamiento "por suerte, siempre lo suficiente".}