syntax - simplificacion - lenguajes regulares pdf

¿Qué es un lenguaje regular?

Question

Estoy intentando 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 lo que es un lenguaje regular y cómo difieren los idiomas?

2. ¿Dónde la gente aprende a entender esto? Según lo entiendo, ¿son las matemáticas formales? Tuve un par de cursos en la universidad que lo usaron y casi nadie lo entendió porque los tutores simplemente 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.

Aquí hay un example :

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

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

Answer 1

Aprendí la mayor parte de ese tipo de cosas de "Introducción a la teoría de la computación", de Michael Sipser ; Lo encontré realmente útil.

Aquí están los contenidos:

• Introducción
• Parte 1: Autómatas e idiomas
  • 1. Idiomas regulares
  • 2. Lenguajes sin contexto
• Parte 2: Teoría de Computabilidad
  • 3. La tesis de Church-Turing
  • 4. Decidabilidad
  • 5. Reducibilidad
  • 6. Temas avanzados en teoría de computabilidad
• Parte 3: Teoría de la Complejidad
  • 7. Complejidad del tiempo
  • 8. Complejidad espacial
  • 9. Intractabilidad
  • 10. Temas avanzados en la teoría de la complejidad.

Answer 2

En el contexto de la informática, una palabra es la concatenación de símbolos . Los símbolos usados ​​se llaman alfabeto . Por ejemplo, algunas palabras formadas fuera 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, tal vez deseemos definir un lenguaje que capture todos los agentes MI6 de élite. Todos comienzan con doble-0, por lo que las palabras en el idioma serían 007 , 001 , 005 y 0012 , pero no 07 o 15 . Por 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 ciencias de la computación, ahora queremos clasificar los idiomas. Llamamos un lenguaje regular si se puede decidir si una palabra está en el lenguaje con un algoritmo / una máquina con memoria constante (finita) al examinar todos los símbolos en la palabra uno tras otro. El lenguaje que consiste solo en la palabra 42 es 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 hay 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 conjunto de declaraciones anónimas if -que examinan un dígito después del otro). 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 idioma double-0 contiene un número infinito de palabras ( 007 , 008 , pero también 004242 y 0012345 ), pero puede probarse con la memoria constante: para comprobar si una palabra pertenece, verifique 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 de código MI6.

Formalmente, la construcción de una máquina de estado finito o una gramática regular se usa para probar que un lenguaje es regular. Estos son similares a las declaraciones if 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 para mostrar cualquiera. 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 por el mismo número de 2 (a menudo escrito como 1 ⁿ 2 ⁿ , para un n arbitrario) 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 generalmente debería explicarse en el curso teórico de informática. Afortunadamente, Wikipedia explica bastante bien tanto en.wikipedia.org/wiki/Formal_language lenguajes en.wikipedia.org/wiki/Formal_language como los regulares .

Answer 3

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 determinista de estados finitos.
• puede ser aceptado por una máquina de estado finito no determinista

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

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

Lo primero a tener en cuenta es que un idioma regular es en.wikipedia.org/wiki/Formal_language , con algunas restricciones. Un lenguaje formal es esencialmente una (posiblemente infinita) colección 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 sin contexto , un idioma normal no admite la anidación / recursión arbitraria, pero sí tiene una 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 es bueno hablar de idiomas sobre otros alfabetos, por ejemplo, el alfabeto binario donde los únicos caracteres permitidos son 0 y 1 .

En mi universidad, nos enseñaron un poco de teoría del lenguaje formal en la clase de compiladores, pero esto es probablemente diferente entre las diferentes escuelas.