chomsky-normal-form

0зной

1ответ

Как решить эту форму Чомского

S → aSab | ABB | BB A → baab | BABB | AaA B → bAaBa | bb | b Я начал ее решать, но, похоже, я просто продолжал добавлять новые правила, чтобы не отставать, может кто-то объяснить, как это сделат

context-free-grammar chomsky-normal-form 2015-04-15

---

0зной

2ответ

Хомский алгоритм преобразования нормальной формы

Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что не так, если мы этого не сделаем? Сначала я думал, что это из-за правил eps

complexity-theory context-free-grammar computation-theory context-free-language chomsky-normal-form 2016-05-31

---

0зной

1ответ

Как вы делаете последний шаг при конвертации CFG в CNF?

Дано: S->AcA|BcB A->ccBc|ABA|cc B->c step1 S0->S S->AcA|BcB A->ccBc|ABA|cc B->c step2 // change symbol to terminals? S0->S S->ABA|BBB A->BBBB|ABA

context-free-grammar chomsky-normal-form 2015-03-13

---

0зной

1ответ

Удаление нулевых производств из контекста свободной грамматики

X -> zZ|yW|WW Y->Z Z->X|ε W->Y|X Я бы правильно думать, что, как только Y Z в качестве его терминала из е перемещается Y подачи: X -> zZ|yW|WW Y->Z|ε Z->X W->Y|X тогда? X -> zZ|yW|WW|z Y->Z

context-free-grammar chomsky-normal-form 2014-12-12

---

1зной

1ответ

Построить контекстную свободную грамматику для языка в нормальной форме Хомского

Я пытаюсь построить CFG в нормальной форме Хомского с максимально возможным количеством произведений, которые допускают язык, содержащий единственную строку a^21. Я понимаю, что я мог бы просто преобр

theory context-free-grammar computation-theory chomsky-normal-form 2016-04-26

---