CFG sta per grammatica libera dal contesto. È una grammatica formale che viene utilizzata per generare tutti i possibili modelli di stringhe in un dato linguaggio formale. La grammatica libera dal contesto G può essere definita da quattro tuple come:
G = (V, T, P, S)
Dove,
G è la grammatica, che consiste in un insieme di regole di produzione. Viene utilizzato per generare la stringa di una lingua.
T è l'insieme finale di un simbolo terminale. È indicato con lettere minuscole.
IN è l'insieme finale di un simbolo non terminale. È indicato con lettere maiuscole.
P è un insieme di regole di produzione, che viene utilizzato per sostituire i simboli non terminali (sul lato sinistro della produzione) in una stringa con altri simboli terminali o non terminali (sul lato destro della produzione).
array di stringhe programmazione c
S è il simbolo iniziale utilizzato per derivare la stringa. Possiamo derivare la stringa sostituendo ripetutamente un non terminale con il lato destro della produzione finché tutti i non terminali non sono stati sostituiti con simboli terminali.
Esempio 1:
Costruisci il CFG per la lingua che ha un numero qualsiasi di a nell'insieme ∑= {a}.
Soluzione:
Come sappiamo l'espressione regolare per la lingua di cui sopra è
r.e. = a*
La regola di produzione per l'espressione regolare è la seguente:
S → aS rule 1 S → ε rule 2
Ora se vogliamo derivare una stringa 'aaaaaa', possiamo iniziare con i simboli iniziali.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Là. = a* può generare un insieme di stringhe {ε, a, aa, aaa,.....}. Possiamo avere una stringa nulla perché S è un simbolo di inizio e la regola 2 dà S → ε.
Esempio 2:
Costruisci un CFG per l'espressione regolare (0+1)*
Soluzione:
gimp salva come jpeg
Il CFG può essere dato da,
Production rule (P): S → 0S | 1S S → ε
Le regole sono nella combinazione di 0 e 1 con il simbolo di inizio. Poiché (0+1)* indica {ε, 0, 1, 01, 10, 00, 11, ....}. In questo insieme, ε è una stringa, quindi nella regola possiamo impostare la regola S → ε.
Esempio 3:
Costruisci un CFG per una lingua L = dove w € (a, b)*.
Soluzione:
La stringa che può essere generata per una determinata lingua è {aacaa, bcb, abcba, bacab, abbcbba, ....}
La grammatica potrebbe essere:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Ora se vogliamo derivare una stringa 'abbcbba', possiamo iniziare con i simboli di inizio.
supw
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Pertanto qualsiasi stringa di questo tipo può essere derivata dalle regole di produzione date.
Esempio 4:
Costruisci un CFG per la lingua L = aNB2ndove n>=1.
Soluzione:
La stringa che può essere generata per una determinata lingua è {abb, aabbbb, aaabbbbbb....}.
La grammatica potrebbe essere:
S → aSbb | abb
Ora se vogliamo derivare una stringa 'aabbbb', possiamo iniziare con i simboli di inizio.
S → aSbb S → aabbbb