Говорят, что набор всех строк, которые могут быть получены из грамматики, является языком, сгенерированным из этой грамматики. Язык, генерируемый грамматикой G, представляет собой подмножество, формально определяемое как
L (G) = {W | W ∈ ∑ *, S ⇒ G W }
Если L (G1) = L (G2) , грамматика G1 эквивалентна грамматике G2 .
пример
Если есть грамматика
G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}
Здесь S производит AB , и мы можем заменить A на a , а B на b . Здесь единственной принятой строкой является ab , т.е.
L (G) = {ab}
пример
Предположим, у нас есть следующая грамматика —
G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA | a, B → bB | b}
Язык, генерируемый этой грамматикой —
L (G) = {ab, a 2 b, ab 2 , a 2 b 2 , ………}
= {a m b n | m ≥ 1 и n ≥ 1}
Построение грамматики, порождающей язык
Мы рассмотрим некоторые языки и преобразуем их в грамматику G, которая производит эти языки.
пример
Задача — Предположим, что L (G) = {a m b n | m ≥ 0 и n> 0}. Мы должны выяснить грамматику G, которая производит L (G) .
Решение
Поскольку L (G) = {a m b n | m ≥ 0 и n> 0}
набор принятых строк может быть переписан как —
L (G) = {b, ab, bb, aab, abb, …….}
Здесь начальный символ должен содержать хотя бы одну букву «b», которой предшествует любое число «a», включая ноль.
Чтобы принять набор строк {b, ab, bb, aab, abb, …….}, Мы взяли продукцию —
S → aS, S → B, B → b и B → bB
S → B → b (принято)
S → B → bB → bb (принято)
S → aS → aB → ab (принято)
S → aS → aaS → aaB → aab (принято)
S → aS → aB → abB → abb (принято)
Таким образом, мы можем доказать, что каждая отдельная строка в L (G) принята языком, сгенерированным производственным набором.
Отсюда и грамматика
G: ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB})
пример
Задача — Предположим, что L (G) = {a m b n | m> 0 и n ≥ 0}. Мы должны выяснить грамматику G, которая производит L (G).
Решение —
Поскольку L (G) = {a m b n | m> 0 и n ≥ 0}, набор принятых строк можно переписать как —
L (G) = {a, aa, ab, aaa, aab, abb, …….}
Здесь начальный символ должен содержать хотя бы одну букву «a», за которой следует любое число «b», включая ноль.
Чтобы принять набор строк {a, aa, ab, aaa, aab, abb, …….}, Мы взяли произведения:
S → aA, A → aA, A → B, B → bB, B → λ
S → aA → aB → aλ → a (принято)
S → aA → aaA → aaB → aaλ → aa (принято)
S → aA → aB → abB → abλ → ab (принято)
S → aA → aaA → aaaA → aaaB → aaaλ → aaa (принято)
S → aA → aaA → aaB → aabB → aabλ → aab (принято)
S → aA → aB → abB → abbB → abbλ → abb (принято)
Таким образом, мы можем доказать, что каждая отдельная строка в L (G) принята языком, сгенерированным производственным набором.
Отсюда и грамматика
G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB})