CFG znamená bezkontextovú gramatiku. Je to formálna gramatika, ktorá sa používa na generovanie všetkých možných vzorov reťazcov v danom formálnom jazyku. Bezkontextová gramatika G môže byť definovaná štyrmi n-ticami ako:
G = (V, T, P, S)
Kde,
G je gramatika, ktorá pozostáva zo sady výrobných pravidiel. Používa sa na generovanie reťazca jazyka.
T je konečná množina symbolu terminálu. Označuje sa malými písmenami.
V je konečná množina nekoncového symbolu. Označuje sa veľkými písmenami.
P je súbor produkčných pravidiel, ktorý sa používa na nahradenie neterminálnych symbolov (na ľavej strane produkcie) v reťazci inými koncovými alebo neterminálnymi symbolmi (na pravej strane produkcie).
mysql odišiel pripojiť
S je počiatočný symbol, ktorý sa používa na odvodenie reťazca. Reťazec môžeme odvodiť opakovaným nahrádzaním neterminálu pravou stranou produkcie, až kým všetky neterminály budú nahradené koncovými symbolmi.
Príklad 1:
Zostrojte CFG pre jazyk, ktorý má ľubovoľný počet a cez množinu ∑= {a}.
Riešenie:
Ako vieme, regulárny výraz pre vyššie uvedený jazyk je
r.e. = a*
Produkčné pravidlo pre regulárny výraz je nasledovné:
S → aS rule 1 S → ε rule 2
Teraz, ak chceme odvodiť reťazec 'aaaaaa', môžeme začať so štartovacími symbolmi.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
R.e. = a* dokáže vygenerovať množinu reťazcov {ε, a, aa, aaa,.....}. Môžeme mať nulový reťazec, pretože S je počiatočný symbol a pravidlo 2 dáva S → ε.
Príklad 2:
Vytvorte CFG pre regulárny výraz (0+1)*
Riešenie:
árijský chán
CFG môže byť daný,
Production rule (P): S → 0S | 1S S → ε
Pravidlá sú v kombinácii 0 a 1 so symbolom štartu. Pretože (0+1)* označuje {ε, 0, 1, 01, 10, 00, 11, ....}. V tejto množine je ε reťazec, takže v pravidle môžeme nastaviť pravidlo S → ε.
Príklad 3:
Zostrojte CFG pre jazyk L = kde w € (a, b)*.
Riešenie:
Reťazec, ktorý je možné vygenerovať pre daný jazyk je {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatika môže byť:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Teraz, ak chceme odvodiť reťazec 'abbcbba', môžeme začať so štartovacími symbolmi.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Z daných výrobných pravidiel je teda možné odvodiť ktorýkoľvek z týchto druhov reťazcov.
najlepšie autá na svete
Príklad 4:
Zostrojte CFG pre jazyk L = anb2nkde n>=1.
Riešenie:
Reťazec, ktorý je možné vygenerovať pre daný jazyk, je {abb, aabbbb, aaabbbbbb....}.
Gramatika môže byť:
S → aSbb | abb
Teraz, ak chceme odvodiť reťazec 'aabbbb', môžeme začať so štartovacími symbolmi.
S → aSbb S → aabbbb