CFG oznacza gramatykę bezkontekstową. Jest to gramatyka formalna, która służy do generowania wszystkich możliwych wzorców ciągów znaków w danym języku formalnym. Gramatykę bezkontekstową G można zdefiniować za pomocą czterech krotek jako:
G = (V, T, P, S)
Gdzie,
G jest gramatyką, na którą składa się zbiór reguł produkcji. Służy do generowania ciągu języka.
T jest ostatnim zestawem symboli końcowych. Jest ona oznaczona małymi literami.
W jest ostatnim zestawem symbolu nieterminalnego. Jest to oznaczone wielkimi literami.
P to zestaw reguł produkcji, który służy do zastępowania symboli nieterminalnych (po lewej stronie produkcji) w ciągu znaków innymi symbolami terminalnymi lub nieterminalowymi (po prawej stronie produkcji).
podział ciągu Java
S jest symbolem początkowym używanym do wyprowadzenia ciągu. Możemy wyprowadzić ciąg, wielokrotnie zastępując symbol nieterminalny prawą stroną produkcji, aż wszystkie symbole nieterminalne zostaną zastąpione symbolami końcowymi.
Przykład 1:
Skonstruuj CFG dla języka mającego dowolną liczbę a w zbiorze ∑= {a}.
Rozwiązanie:
Jak wiemy, wyrażenie regularne dla powyższego języka to
r.e. = a*
Reguła tworzenia wyrażenia regularnego jest następująca:
S → aS rule 1 S → ε rule 2
Teraz, jeśli chcemy wyprowadzić ciąg „aaaaaa”, możemy zacząć od symboli początkowych.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Tam. = a* może wygenerować zbiór ciągów {ε, a, aa, aaa,.....}. Możemy mieć ciąg zerowy, ponieważ S jest symbolem startu, a reguła 2 daje S → ε.
Przykład 2:
Skonstruuj CFG dla wyrażenia regularnego (0+1)*
Rozwiązanie:
algorytmy sortowania przez wstawianie
CFG można podać m.in.
Production rule (P): S → 0S | 1S S → ε
Zasady są kombinacją zer i jedynek z symbolem startu. Ponieważ (0+1)* oznacza {ε, 0, 1, 01, 10, 00, 11, ....}. W tym zbiorze ε jest ciągiem, więc w regule możemy ustawić regułę S → ε.
Przykład 3:
Skonstruuj CFG dla języka L = gdzie w € (a, b)*.
Rozwiązanie:
Ciąg znaków, który można wygenerować dla danego języka to {aacaa, bcb, abcba, bacab, abbcbba, ....}
Gramatyka może wyglądać następująco:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Teraz, jeśli chcemy wyprowadzić ciąg „abbcbba”, możemy zacząć od symboli początkowych.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Zatem dowolny tego rodzaju ciąg można wyprowadzić z podanych reguł produkcji.
ciąg zastępczy Java
Przykład 4:
Skonstruuj CFG dla języka L = aNB2ngdzie n>=1.
Rozwiązanie:
Ciąg znaków, który można wygenerować dla danego języka to {abb, aabbbb, aaabbbbbb....}.
Gramatyka może wyglądać następująco:
S → aSbb | abb
Teraz, jeśli chcemy wyprowadzić ciąg „aabbbb”, możemy zacząć od symboli początkowych.
S → aSbb S → aabbbb