Здравствуйте, я хотел бы задать вам этот вопрос.
Я должен был вычислить (вручную) грамматику в нормальной форме Грейбаха, которая генерирует язык
L = {ai bj ck | i + j = 2k and k >= 1}
Я действительно понятия не имею,. Кто-нибудь может мне помочь?
Заранее спасибо
Крисс
Context Free Grammar CFG для вашего языка La = {ai bj ck | i + j = 2k and k >= 1}.
Ниже ответ на языке L = {ai bj ck | i + j = k and k >= 1}.
Конфигурация:
S --> aAc | bBc |
A --> aAc | B | ^
B --> bBc | ^
Что такое GNF?
Одной из важных форм CFG является нормальная форма Greibach GNF:
A --> aα
Where α ∈ V* (any number of variables including zero)
Примечание: nul ^ не может быть символом в правой части любой продукции. Примите начальный символ S с условием, что если S --> ^ является постановкой в грамматике, то S не может появляться в правой части любой другой продукции в грамматика.
Любая CFG может быть записана в форме GNF.
Как конвертировать CFG в GNF?
Обратите внимание, что в CFG, который я написал выше, есть нулевые производства A --> ^ и B --> ^ и единичное производство A --> B. Единичные и нулевые производства не допускаются в форме GNF. Хотя другие продукты могут быть легко записаны в форме GNF путем введения в продукты GNF в грамматике, например. S --> aAc можно переписать как S --> aAC and C --> c.
Итак, ниже я переписываю эквивалентную CFG для языка и удаляю nul и единицы продукции, называемые упрощенной CFG.
Упрощенная конфигурация конфигурации:
S --> aAc | bBc | ac | bc
A --> aAc | bBc
B --> bBc | bc
Теперь эту грамматику можно легко преобразовать в форму GNF, введя новую продукцию GNF C --> c и заменив c на C в других правилах продукции.
GFN для языка L:
S --> aAC | bBC | aC | bC
A --> aAC | bBC
B --> bBC | bC
C --> c
По ошибке я написал неправильную грамматику, я обновлю ответ для языка La
Изменить
La = {ai bj ck | i + j = 2k and k >= 1}.
CFG для La:
S --> aaAc | bbBc | abBc
A --> aaAc | B | abBc | ^
B --> bbBc | ^
Упрощенная конфигурация конфигурации:
S --> aaAc | bbBc | abBc | aac | bbc | abc
A --> aaAc | bbBc | abBc | aac | abc
B --> bbBc | bbc
GFN для языка La:
Добавьте три новых производственных правила: X --> a, Y --> b и Z --> c.
Сменить программатор и заменить терминал на переменные:
S --> aXAZ | bYBZ | aYBZ | aAZ | bYZ | aYZ
A --> aXAZ | bYBZ | aYBZ | aXZ | aYZ
B --> bYBZ | bYZ
X --> a
Y --> b
Z --> c
О приведенном ниже ответе CFG La = {ai bj ck | i + j = k and k >= 1} неверен
Ваш упрощенный CFG:
S --> aAc | bBc | ac | bc .
A --> aAc | bBc .
B --> bBc | bc .
Поскольку приведенный выше язык L = {ai bj ck | i + j = k and k >= 1} создает язык aabccc, но ваш упрощенный CFG не создает его.
Правый CFG
Упрощенная CFG
S --> aAc | bBc | ac | bc
A --> aAc | bBc | bc | ac
B --> bBc | bc
Исправьте это, второй язык имеет ту же проблему.
Спасибо!
