CFG znamená bezkontextovou gramatiku. Je to formální gramatika, která se používá ke generování všech možných vzorů řetězců v daném formálním jazyce. Bezkontextová gramatika G může být definována čtyřmi n-ticemi jako:
G = (V, T, P, S)
Kde,
G je gramatika, která se skládá ze sady produkčních pravidel. Používá se ke generování řetězce jazyka.
T je konečná sada symbolu terminálu. Označuje se malými písmeny.
V je konečná sada nekoncového symbolu. Označuje se velkými písmeny.
P je sada produkčních pravidel, která se používá pro nahrazení neterminálních symbolů (na levé straně produkce) v řetězci jinými koncovými nebo neterminálními symboly (na pravé straně produkce).
inurl:.git/head
S je počáteční symbol, který se používá k odvození řetězce. Řetězec můžeme odvodit opakovaným nahrazením neterminálu pravou stranou produkce, dokud nebudou všechny neterminálové symboly nahrazeny koncovými symboly.
Příklad 1:
Sestrojte CFG pro jazyk, který má libovolný počet a přes množinu ∑= {a}.
Řešení:
Jak víme, regulární výraz pro výše uvedený jazyk je
r.e. = a*
Produkční pravidlo pro regulární výraz je následující:
S → aS rule 1 S → ε rule 2
Nyní, pokud chceme odvodit řetězec 'aaaaaa', můžeme začít se startovacími symboly.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Tam. = a* může generovat množinu řetězců {ε, a, aa, aaa,.....}. Můžeme mít nulový řetězec, protože S je počáteční symbol a pravidlo 2 dává S → ε.
Příklad 2:
Vytvořte CFG pro regulární výraz (0+1)*
Řešení:
řádek vs sloupec
CFG může být dáno,
Production rule (P): S → 0S | 1S S → ε
Pravidla jsou v kombinaci 0 a 1 se symbolem startu. Protože (0+1)* označuje {ε, 0, 1, 01, 10, 00, 11, ....}. V této množině je ε řetězec, takže v pravidle můžeme nastavit pravidlo S → ε.
Příklad 3:
Sestrojte CFG pro jazyk L = kde w € (a, b)*.
Řešení:
Řetězec, který lze pro daný jazyk vygenerovat, je {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatika by mohla být:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Nyní, pokud chceme odvodit řetězec 'abbcbba', můžeme začít se startovacími symboly.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Z daných produkčních pravidel lze tedy odvodit jakýkoli tento druh řetězce.
Příklad 4:
Sestrojte CFG pro jazyk L = anb2nkde n>=1.
Řešení:
Řetězec, který lze pro daný jazyk vygenerovat, je {abb, aabbbb, aaabbbbbb....}.
Gramatika by mohla být:
tlačítko uprostřed css
S → aSbb | abb
Nyní, pokud chceme odvodit řetězec 'aabbbb', můžeme začít s počátečními symboly.
S → aSbb S → aabbbb