in

Introducción a las gramáticas

En el sentido literario del término, las gramáticas denotan reglas sintácticas para la conversación en lenguajes naturales. La lingüística ha intentado definir las gramáticas desde el inicio de los lenguajes naturales como el inglés, el sánscrito, el mandarín, etc.

La teoría de los lenguajes formales encuentra su aplicabilidad ampliamente en los campos de la informática. Noam Chomsky dio un modelo matemático de gramática en 1956 que es eficaz para escribir lenguajes informáticos.

Gramática

Una gramática GRAMO se puede escribir formalmente como una tupla de 4 (N, T, S, P) donde –

  • norte o Vnorte es un conjunto de variables o símbolos no terminales.

  • T o es un conjunto de símbolos de Terminal.

  • S es una variable especial llamada símbolo de inicio, S ∈ N

  • PAG es reglas de producción para terminales y no terminales. Una regla de producción tiene la forma α → β, donde α y β son cadenas en Vnorte ∪ ∑ y al menos un símbolo de α pertenece a Vnorte.

Ejemplo

Gramática G1 –

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Aquí,

  • S, A, y B son símbolos no terminales;

  • a y B son símbolos de terminal

  • S es el símbolo de inicio, S ∈ N

  • Producciones, P: S → AB, A → a, B → b

Ejemplo

Gramática G2 –

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Aquí,

  • S y A son símbolos no terminales.

  • a y B son símbolos de terminal.

  • ε es una cadena vacía.

  • S es el símbolo de inicio, S ∈ N

  • Producción P: S → aAb, aA → aaAb, A → ε

Derivaciones de una gramática

Las cadenas pueden derivarse de otras cadenas utilizando las producciones en una gramática. Si una gramática GRAMO tiene una produccion α → β, podemos decir eso x α y deriva x β y en GRAMO. Esta derivación se escribe como:

x α y GRAMO x β y

Ejemplo

Consideremos la gramática:

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Algunas de las cadenas que se pueden derivar son:

S ⇒ Automóvil club británicoB utilizando producción S → aAb

⇒ unaAutomóvil club británicocama y desayuno utilizando producción aA → aAb

⇒ aaaAbbb utilizando producción aA → aaAb

⇒ aaabbb usando producción A → ε

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Cómo configurar Steam VR en Linux

apple touch icon@2

javascript: cómo recorrer una matriz que contiene objetos y acceder a sus propiedades