CFG означава контекстно-свободна граматика. Това е формална граматика, която се използва за генериране на всички възможни модели на низове в даден формален език. Безконтекстната граматика G може да бъде дефинирана от четири кортежа като:
G = (V, T, P, S)
Където,
Ж е граматиката, която се състои от набор от производствени правила. Използва се за генериране на низ на език.
T е окончателният набор от терминален символ. Обозначава се с малки букви.
IN е крайният набор от нетерминален символ. Обозначава се с главни букви.
П е набор от производствени правила, който се използва за замяна на нетерминални символи (от лявата страна на продукцията) в низ с други терминални или нетерминални символи (от дясната страна на продукцията).
дължина на java низ
С е началният символ, който се използва за извличане на низа. Можем да извлечем низа чрез многократно заместване на не-терминал от дясната страна на продукцията, докато всички не-терминали бъдат заменени с терминални символи.
Пример 1:
Конструирайте CFG за езика, който има произволен брой a над множеството ∑= {a}.
Решение:
Както знаем, регулярният израз за горния език е
r.e. = a*
Правилото за създаване на регулярния израз е както следва:
S → aS rule 1 S → ε rule 2
Сега, ако искаме да извлечем низ 'aaaaaa', можем да започнем с начални символи.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Там. = a* може да генерира набор от низ {ε, a, aa, aaa,.....}. Можем да имаме нулев низ, защото S е начален символ и правило 2 дава S → ε.
Пример 2:
Конструирайте CFG за регулярния израз (0+1)*
Решение:
пролетен ботуш
CFG може да бъде даден от,
Production rule (P): S → 0S | 1S S → ε
Правилата са в комбинация от 0 и 1 със символа за начало. Тъй като (0+1)* показва {ε, 0, 1, 01, 10, 00, 11, ....}. В това множество ε е низ, така че в правилото можем да зададем правилото S → ε.
Пример 3:
Конструирайте CFG за език L = където w € (a, b)*.
Решение:
Низът, който може да бъде генериран за даден език, е {aacaa, bcb, abcba, bacab, abbcbba, ....}
Граматиката може да бъде:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Сега, ако искаме да извлечем низ 'abbcbba', можем да започнем с начални символи.
равенство на низове в java
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Така всеки от този вид низ може да бъде извлечен от дадените производствени правила.
Пример 4:
Конструирайте CFG за езика L = aнb2nкъдето n>=1.
Решение:
Низът, който може да бъде генериран за даден език, е {abb, aabbbb, aaabbbbbb....}.
Граматиката може да бъде:
S → aSbb | abb
Сега, ако искаме да извлечем низ 'aabbbb', можем да започнем с начални символи.
S → aSbb S → aabbbb