¿Qué es un idioma regular?

Estoy tratando de comprender el concepto de niveles de idiomas (regular, sin contexto, sensible al contexto, etc.).

Puedo buscar esto fácilmente, pero todas las explicaciones que encuentro son un montón de símbolos y hablan de conjuntos . Tengo dos preguntas:

1. ¿Puede describir con palabras qué es un idioma regular y en qué se diferencian los idiomas?

2. ¿Dónde aprende la gente a entender estas cosas? Según tengo entendido, ¿son matemáticas formales? Tuve un par de cursos en la universidad que lo usaron y casi nadie lo entendió, ya que los tutores asumieron que lo sabíamos. ¿Dónde puedo aprenderlo y por qué se "espera" que la gente lo sepa en tantas fuentes? Es como si hubiera una brecha en la educación.

He aquí un ejemplo :

Cualquier idioma que pertenezca a este conjunto es un idioma regular sobre el alfabeto.

¿Cómo puede un idioma "superar" algo?

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

Un lenguaje es entonces un subconjunto de todas las palabras posibles. Por ejemplo, podríamos querer definir un lenguaje que capture a todos los agentes de élite del MI6. Aquellos todo el comienzo con doble 0, por lo que las palabras en la lengua serían 007, 001, 005, y 0012, aunque no 07o 15. En aras de la simplicidad, decimos que un idioma está " sobre un alfabeto" en lugar de "un subconjunto de palabras formadas por la concatenación de símbolos en un alfabeto".

En informática, ahora queremos clasificar los lenguajes. Llamamos regular a un lenguaje 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 de la palabra uno tras otro. El lenguaje que consiste solo en la palabra 42es regular, ya que puede decidir si una palabra está en él sin requerir cantidades arbitrarias de memoria; simplemente verifica si el primer símbolo es 4, si el segundo es 2 y si siguen más números.

Todos los lenguajes 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 ifdeclaraciones anidadas que examinan un dígito tras otro). Por ejemplo, podemos probar si una palabra está en el lenguaje de "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 lenguajes finitos son regulares, pero no todos los lenguajes regulares son finitos; nuestra doble 0 lenguaje contiene un número infinito de palabras ( 007, 008sino también 004242y 0012345), pero puede ser probado con la memoria constante: Para probar si una palabra pertenece en ella, con un aspa si el primer símbolo es 0, y si el segundo símbolo es 0. Si ese es el caso, acéptelo. Si la palabra es más corta que tres o no comienza con 00, no es un nombre de código MI6.

Formalmente, la construcción de una máquina de estados finitos o una gramática regular se usa para demostrar que un lenguaje es regular. Son similares a las ifdeclaraciones -de arriba, pero permiten palabras arbitrariamente largas. Si hay una máquina de estados finitos, también hay una gramática regular, y viceversa, por lo que es suficiente mostrar cualquiera de las dos. Por ejemplo, la máquina de estados finitos para nuestro lenguaje doble 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 no son regulares. Por ejemplo, el idioma de cualquier número de 1, seguido del mismo número de 2(a menudo escrito como 1 ⁿ 2 ⁿ , para una n arbitraria ) no es regular; necesita más que una cantidad constante de memoria (= un número constante de estados ) para almacenar el número de 1s para decidir si una palabra está o no en el idioma.

Por lo general, esto debe explicarse en el curso de informática teórica. Afortunadamente, Wikipedia explica muy bien los lenguajes formales y regulares .

Estas son algunas de las definiciones equivalentes de Wikipedia :

[...] un lenguaje regular es un lenguaje formal (es decir, un conjunto posiblemente infinito de secuencias finitas de símbolos de un alfabeto finito) que satisface las siguientes propiedades equivalentes:

• puede ser aceptado por una máquina de estados finitos determinista.
• puede ser aceptado por una máquina de estados finitos no determinista

• se puede describir mediante una expresión regular formal.

  Tenga en cuenta que las características de "expresión regular" que se proporcionan con muchos lenguajes de programación se complementan con características que los hacen capaces de reconocer lenguajes que no son regulares y, por lo tanto, no son estrictamente equivalentes a expresiones regulares formales.

Lo primero a tener en cuenta es que un idioma regular es un idioma formal , con algunas restricciones. Un lenguaje formal es esencialmente una colección (posiblemente infinita) de cadenas. Por ejemplo, el lenguaje formal Java es la colección de todos los archivos Java posibles, que es un subconjunto de la colección de todos los archivos de texto posibles.

Una de las características más importantes es que, a diferencia de los lenguajes libres de contexto , un lenguaje normal no admite anidación / recursión arbitraria, pero sí tiene repetición arbitraria.

Un idioma siempre tiene un alfabeto subyacente que es el conjunto de símbolos permitidos. Por ejemplo, el alfabeto de un lenguaje de programación normalmente sería ASCII o Unicode, pero en la teoría del lenguaje formal también está bien hablar de lenguajes en lugar de otros alfabetos, por ejemplo, el alfabeto binario donde los únicos caracteres permitidos son 0y 1.

En mi universidad, nos enseñaron algo de teoría del lenguaje formal en la clase de Compiladores, pero esto probablemente sea diferente entre las diferentes escuelas.