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 G se puede escribir formalmente como una tupla de 4 (N, T, S, P) donde -
N o VN 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
Pes reglas de producción para terminales y no terminales. Una regla de producción tiene la forma α → β, donde α y β son cuerdas en V N ∪ Σ y menos un símbolo de α pertenece a V N .
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 terminales.
ε 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áticaG tiene una produccion α → β, podemos decir eso x α y deriva x β y en G. Esta derivación se escribe como:
x α y ⇒G 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 ⇒ aA b usando producción S → aAb
⇒ a aA bb usando producción aA → aAb
⇒ aaa A bbb usando producción aA → aAb
⇒ aaabbb usando producción A → ε