Lenguajes regulares y expresiones regulares

Dificultad
Fácil 25%

Lenguajes regulares y expresiones regulares

Hay dos tipos de expresiones regulares.

Recordamos que un gramática G1 = (T, N, S, R) es una expresión regular por la derecha si las reglas de R son de la forma: A → aB o A → a con A, B ∈ N y a ∈ T.

Recuerde que una gramática G2 = (T, N, S, R) es una expresión regular de la izquierda si las reglas de R son de la forma: A → Ba o A → a con A, B ∈ N y a ∈ T.

Un idioma es regular o racional si y solo si existe una gramática regular que genera este idioma.

La ventaja de distinguir gramáticas regulares a la derecha o a la izquierda aparece durante el análisis: si leemos los símbolos de la palabra a analizar de izquierda a derecha, entonces

  • Se utilizará una gramática normal de la mano derecha para un análisis de arriba hacia abajo, desde el axioma hasta la palabra.
  • Se utilizará una gramática normal de la mano izquierda para un análisis de abajo hacia arriba, desde la palabra hasta el axioma.

Por ejemplo, para analizar la palabra aaabb con la gramática G1, construiremos la derivación S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb; mientras que para analizar esta palabra con la gramática G2, construiremos la derivación aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2.

Lenguaje y expresion

Una expresión E es una expresión regular en un alfabeto A si y solo si:

  • E = ∅ o
  • E = ε o
  • E = a con a ∈ A o
  • E = E1 | E2 y E1 y E2 son dos expresiones regulares en A o
  • E = E1.E2 y E1 y E2 son dos expresiones regulares en A o
  • E = E1 Verano1 es una expresión regular en A

Los operadores ∗ ,. y | tienen prioridad decreciente. Si es necesario, se pueden agregar paréntesis.

El lenguaje L (E) descrito por una expresión regular E definida en un alfabeto A está definido por

  • L (E) = ∅ si E = ∅,
  • L (E) = {ε} si E = ε,
  • L (E) = {a} si E = a,
  • L (E) = L (E1) ∪ L (E2) si E = E1 | E2,
  • L (E) = L (E1) .L (E2) si E = E1.E2,
  • L (E) = L (E1) si E = E1 Verano1 es una expresión regular en A.

La equivalencia entre expresiones regulares y lenguajes regulares se establece por las siguientes dos implicaciones:

  • Cualquier expresión regular describe un idioma regular.
  • Cualquier idioma regular puede describirse mediante una expresión regular.

Lista de equivalencias trivial:

expresiones regulares

Proceso de creación de un autómata a partir de una expresión regular.

expresión regular