Язык, порожденный грамматикой

Набор всех строк, которые могут быть получены из грамматики, называется языком, созданным из этой грамматики. Язык, созданный грамматикой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 ² b, ab ² , a ² b ² , ………}

= {a ^m b ⁿ | m ≥ 1 и n ≥ 1}

Построение грамматики, порождающей язык

Мы рассмотрим некоторые языки и преобразуем это в грамматику G, которая производит эти языки.

пример

Problem- Предположим, что L (G) = {a ^m b ⁿ | m ≥ 0 и n> 0}. Нам нужно узнать грамматикуG который производит L(G).

Solution

Поскольку L (G) = {a ^m b ⁿ | m ≥ 0 и n> 0}

принятый набор строк можно переписать как -

L (G) = {b, ab, bb, aab, abb, …….}

Здесь начальный символ должен содержать как минимум одну букву «b», перед которой стоит любое количество «а», включая ноль.

Чтобы принять набор строк {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})

пример

Problem- Предположим, что L (G) = {a ^m b ⁿ | m> 0 и n ≥ 0}. Нам нужно найти грамматику G, которая дает L (G).

Solution -

Поскольку L (G) = {a ^m b ⁿ | 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})