Introduzione alle grammatiche
Nel senso letterario del termine, le grammatiche denotano regole sintattiche per la conversazione nelle lingue naturali. La linguistica ha tentato di definire le grammatiche sin dall'inizio delle lingue naturali come l'inglese, il sanscrito, il mandarino, ecc.
La teoria dei linguaggi formali trova la sua applicabilità ampiamente nei campi dell'informatica. Noam Chomsky ha fornito un modello matematico di grammatica nel 1956 che è efficace per la scrittura di linguaggi informatici.
Grammatica
Una grammatica G può essere formalmente scritto come una tupla di 4 (N, T, S, P) dove -
N o VN è un insieme di variabili o simboli non terminali.
T o ∑ è un insieme di simboli di terminale.
S è una variabile speciale chiamata simbolo Start, S ∈ N
Pè Regole di produzione per terminali e non terminali. Una regola di produzione ha la forma α → β, dove α e β sono stringhe su V N ∪ Σ e almeno un simbolo di α appartiene V N .
Esempio
Grammatica G1 -
({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})
Qui,
S, A, e B sono simboli non terminali;
a e b sono simboli terminali
S è il simbolo Start, S ∈ N
Produzioni, P : S → AB, A → a, B → b
Esempio
Grammatica G2 -
(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})
Qui,
S e A sono simboli non terminali.
a e b sono simboli terminali.
ε è una stringa vuota.
S è il simbolo Start, S ∈ N
Produzione P : S → aAb, aA → aaAb, A → ε
Derivazioni da una grammatica
Le stringhe possono essere derivate da altre stringhe utilizzando le produzioni in una grammatica. Se una grammaticaG ha una produzione α → β, possiamo dirlo x α y deriva x β y nel G. Questa derivazione è scritta come -
x α y ⇒G x β y
Esempio
Consideriamo la grammatica -
G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})
Alcune delle stringhe che possono essere derivate sono:
S ⇒ aA b utilizzando la produzione S → aAb
⇒ a aA bb utilizzando la produzione aA → aAb
⇒ aaa A bbb utilizzando la produzione aA → aAb
⇒ aaabbb utilizzando la produzione A → ε