¿Qué es un idioma regular?

En el contexto de la informática, una palabra es la concatenación de símbolos. Los símbolos usados se llaman el alfabeto . Por ejemplo, algunas palabras se formó a partir del alfabeto {0,1,2,3,4,5,6,7,8,9} sería 1, 2, 12, 543, 1000, y 002.

Un lenguaje es entonces un subconjunto de todas las palabras posibles. Por ejemplo, podríamos definir un lenguaje que capture a todos los agentes elite MI6. Todos comienzan con doble-0, por lo que las palabras en el idioma ser 007, 001, 005, y 0012, pero no 07 o 15. Para simplificar, decimos que un lenguaje es " sobreun alfabeto" en lugar de "un subconjunto de palabras formado por la concatenación de símbolos en un alfabeto".

En informática, ahora queremos clasificar idiomas. Llamamos a un lenguaje regular si se puede decidir si una palabra está en el lenguaje con un algoritmo/una máquina con memoria constante (finita) examinando todos los símbolos en la palabra uno después de otro. El lenguaje que consiste solo en la palabra 42 es regular, ya que puede decidir si una palabra está en ella sin requerir cantidades arbitrarias de memoria; solo verifique si el primer símbolo es 4, si el segundo es 2 y si le siguen más números.

Todos los idiomas con un número finito de palabras son regulares, porque podemos (en teoría) simplemente construir un árbol de flujo de control de tamaño constante (puede visualizarlo como un montón de if sentencias anidadas que examinan un dígito después de la otra). Por ejemplo, podemos probar si una palabra está en el lenguaje "números primos entre 10 y 99" con la siguiente construcción, que no requiere memoria, excepto la que codifica en qué línea de código estamos actualmente:

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

Tenga en cuenta que todos los idiomas finitos son regulares, pero no todos los idiomas regulares son finitos; nuestro lenguaje doble-0 contiene un número infinito de palabras (007, 008, pero también 004242 y 0012345), pero se puede probar con memoria constante: Para probar si una palabra pertenece en él, compruebe si el primer símbolo es 0, y si el segundo símbolo es 0. Si ese es el caso, acéptalo. Si la palabra es más corta que tres o no comienza con 00, no es un nombre en código MI6.

Formalmente, la construcción de una máquina de estados finitos o una gramática regular se utiliza para demostrar que un lenguaje es regular. Estas son similares a las if-declaraciones anteriores, pero permiten palabras arbitrariamente largas. Si hay una máquina de estado finito, también hay una gramática regular, y viceversa, por lo que es suficiente mostrar cualquiera. Por ejemplo, la máquina de estados finitos para nuestro lenguaje double-0 es:

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

La gramática regular equivalente es:

start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...

La expresión regular equivalente es:

00[0-9]*

Algunos idiomas son no regulares. Por ejemplo, el lenguaje de cualquier número de 1, seguido por el mismo número de 2 (a menudo escrito como 1ⁿ2ⁿ, para cualquier n) no es regular - se necesita más que una cantidad constante de memoria(= un número constante de estados) para almacenar el número de 1 s para decidir si una palabra está o no en el idioma.

Esto debería explicarse generalmente en el curso teórico de ciencias de la computación. Afortunadamente, Wikipedia explica ambos formal y regular idiomas bastante bien.