Sono un modo di descrivere linguaggi. Permettono di descrivere caratteristiche ricorsive delle stringhe riconosciute. Per questo sono utili per descrivere linguaggi umani e linguaggi di programmazione.

Una grammatica acontestuale consiste in un insieme di regole di sostituzione, anche chiamate produzioni, scritte nel formato . Le variabili (indicate con lettere maiuscole) sono simboli da sostituire, mentre le stringhe sono sequenze di variabili e terminali, altri simboli dell’alfabeto. Una delle variabili è la variabile iniziale, scritta a sinistra nella prima regola.

Esempio di derivazione (sequenza di simboli per ottenere una stringa) di “00#11” nella seguente grammatica:

Si dice che genera ; scritto come: .

N.B.: Più regole e possono essere abbreviate in .

Linguaggi acontestuali

Il linguaggio di una grammatica acontestuale, cioè l’insieme di tutte le stringhe che possono essere generate dalla suddetta grammatica, è detto context free language (linguaggio acontestuale).

I linguaggi regolari sono linguaggi acontestuali.

dadimostrare

Definizioni formali

Una grammatica acontestuale è una quadrupla dove:

  • sono le variabili. Esse non sono simboli dell’alfabeto,
  • è l’alfabeto,
  • solo le regole,
  • è la variabile iniziale.

Il linguaggio di una grammatica acontestuale è .

La derivazione di una stringa di una grammatica si dice derivazione leftmost se a ogni step la variabile più a sinistra della stringa viene rimpiazzata.

Una stringa si dice derivata ambiguamente in una grammatica acontestuale se ha una o più dericazioni leftmost.

Una grammatica si dice ambigua se genera ambiguamente almeno una stringa.

Esercizi: formalizzare le descrizioni dei seguenti linguaggi in CFG

1.

Stringhe binarie con almeno 3 uno

2.

vuol dire palindroma.

3.

?

Implementazione mia su python

def derive_from(string, grammar, iterations, i=0, path=None):
    if path is None:
        path = []
    if i > iterations:
        return
    if not any([var in string for var in grammar.keys()]):
        print(*path, string, sep=' -> ')
    for variable, substitutions in grammar.items():
        if variable in string:
            for substitution in substitutions:
                path.append(string)
                derive_from(
                    string.replace(variable, substitution, 1),
                    grammar,
                    iterations,
                    i+1,
                    path
                )
                path.pop()
 
G = {
    'A': ['0A1', 'B'],
    'B': ['#']
}
 
derive_from('A', G, 5)

output:

A -> 0A1 -> 00A11 -> 000A111 -> 000B111 -> 000#111
A -> 0A1 -> 00A11 -> 00B11 -> 00#11
A -> 0A1 -> 0B1 -> 0#1
A -> B -> #

Altro esempio

G = {
    'START': ['Hi! SENTENCE'],
    'SENTENCE': ['I am PERSON', 'I know a PERSON', 'have a nice TIME in PLACE!', 'I really like ACTIVITY in PLACE', 'I really like ACTIVITY in PLACE in the TIME'],
    'PLACE': ['Rome', 'Paris'],
    'TIME': ['morning', 'evening'],
    'PERSON': ['a GENDER who PREFERENCE ACTIVITY in the TIME', 'a GENDER from PLACE who PREFERENCE ACTIVITY in the TIME'],
    'PREFERENCE': ['likes', 'hates', 'would like'],
    'GENDER': ['boy', 'girl'],
    'ACTIVITY': ['running', 'skating', 'singing']
}
 
derive_from('START', G, 8)
 
# Esempi output:
# Hi! have a nice time in Paris!
# Hi! I know a girl from Rome who likes singing in the morning
# Hi! I really like skating in Rome