COMPARTE ESTE ARTÍCULO

A continuación, se presentan diversas gramáticas y expresiones utilizadas en el estudio de lenguajes formales y teoría de la computación. Cada ejercicio muestra una gramática que genera un lenguaje específico, junto con los símbolos y reglas de producción que definen sus estructuras. Estas definiciones son ideales para entender cómo se construyen diferentes lenguajes y expresiones en un contexto formal.

Ejercicio 1: Gramática para L = { a^n b^n | n >= 0 }

Esta gramática genera cadenas en las que el número de símbolos “a” es igual al número de símbolos “b”, y los “a” preceden a los “b”.

Reglas de Producción:

  S -> aSb
  S -> ε

Ejercicio 2: Gramática para L = { a^n b^m | n, m >= 0, n != m }

Esta gramática genera cadenas en las que la cantidad de “a” es diferente de la cantidad de “b”.

Reglas de Producción:

  S -> A | B
  A -> aAb | aA | a
  B -> bBa | bB | b

Ejercicio 3: Gramática para L = { ww^R | w pertenece a {a, b}* }

Esta gramática genera cadenas que son palíndromos, es decir, cadenas que se leen igual de izquierda a derecha y de derecha a izquierda.

Reglas de Producción:

  S -> aSa
  S -> bSb
  S -> ε

Ejercicio 4: Gramática para L = { a^n b^m c^n | n >= 0, m impar }

Esta gramática genera cadenas en las que el número de “a” es igual al número de “c”, y la cantidad de “b” es impar.

Reglas de Producción:

  S -> aSc | T
  T -> bU
  U -> bU | ε

Ejercicio 5: Gramática para L = { a^n b^m c^m d^n | n, m >= 1 }

Esta gramática genera cadenas en las que el número de “a” es igual al número de “d”, y el número de “b” es igual al número de “c”.

Reglas de Producción:

  S -> aSd | AB
  A -> bA | b
  B -> cB | c

Ejercicio 6: Gramática para L = { a^n b^m | n > m >= 0 }

Esta gramática genera cadenas en las que la cantidad de “a” es mayor que la cantidad de “b”.

Reglas de Producción:

  S -> aS | aA
  A -> bA | ε

Ejercicio 7: Gramática para L = { a^i b^j c^(i+j) | i, j >= 1, i + j par }

Esta gramática genera cadenas en las que el número de “c” es igual a la suma de “a” y “b”, y esa suma es par.

Reglas de Producción:

  S -> aBc
  B -> bBc | b

Ejercicio 8: Expresiones Booleanas

Esta gramática define expresiones booleanas básicas utilizando operadores lógicos comunes.

Reglas de Producción:

  S -> S AND S
  S -> S OR S
  S -> NOT S
  S -> (S)
  S -> true
  S -> false

Ejercicio 9: Expresiones Aritméticas Simples

Esta gramática define expresiones aritméticas básicas que incluyen operaciones de suma y productos.

Reglas de Producción:

  E -> E + T | T
  T -> T * F | F
  F -> (E) | num

Ejercicio 10: Listas Anidadas

Esta gramática define listas anidadas, permitiendo listas dentro de otras listas.

Reglas de Producción:

  L -> [L] | [E] | ε
  E -> E, E | num

Este artículo presenta cada conjunto de reglas de producción junto con una breve descripción, lo que facilita la comprensión de los lenguajes y expresiones que cada gramática representa.

Photo by Pavel Danilyuk on Pexels.com
Photo by RealToughCandy.com on Pexels.com
Photo by Andrea Piacquadio on Pexels.com

¿QUÉ TE HA PARECIDO EL ARTÍCULO? Danos tu opinión al final de la página.
Deja tu comentario y ayúdanos a crecer.

¡SÍGUENOS EN TUS REDES FAVORITAS!
AYUDANOS A CRECER Y QUE LLEGUEMOS A TODAS LAS PERSONAS QUE NOS NECESITANA. SÍGUENOS EN TUS REDES.
Entra AQUÍ y elíge donde seguirnos.