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

Question

Я знаю, что это не общий вопрос, но я хотел бы знать, как это сделать, используя пример, над которым я уже немного работал.. Однажды сказал это:

У меня есть следующая грамматика. Я пытался упростить его, но я не уверен в его правильности. Может ли кто-нибудь помочь мне подтвердить, правильно это или нет?

S -> BC | lambda
A -> aA | lambda
B -> bB
C -> c

Если мне нужно упростить грамматику, я сначала применяю лямбда-исключения, когда у меня есть что-то вроде:

S -> BC | B | C
A -> aA | a
B -> bB
C -> c

И, наконец, я должен устранить ненужные символы: сначала я удаляю те, которые не являются продуктивными, а затем те, которые недоступны, так что..

S -> BC | bB | C
A -> aA | a
B -> bB  ---> non-productive
C -> c

S -> C | b | C
A -> aA | a --> unreacheable
C -> c

Наконец, у меня есть что-то вроде этого, и я исключаю C, потому что это не нужно, и я также исключаю BC, потому что были устранены, поэтому должно быть что-то вроде: S -> b | с

Но если я честен, я не думаю, что то, что я сделал, правильно, но я не знаю точно

Answer 1

Похоже, могут быть некоторые проблемы с вашим упрощением - или у меня возникают проблемы с его выполнением. Я пойду через то, что я буду делать, и вы сравните с вашим пониманием.

S -> BC | lambda
A -> aA | lambda
B -> bB
C -> c

Я предполагаю, что цель состоит в том, чтобы устранить как можно больше lambda и нетерминальные символы, насколько это возможно. Первое, что нужно отметить, это то, что производство S -> lambda не может быть устранено без изменения языка; но все остальные lambda производства могут быть устранены. Мы видим еще одно производство, поэтому мы уверены, что оно может быть ликвидировано. Как мы устраняем A -> lambda?

Мы отмечаем, что A недоступен из S, начальный символ. Таким образом, мы можем довольно легко устранить A -> lambda устраняя A в целом. Мы приходим к этой более простой эквивалентной грамматике:

S -> BC | lambda
B -> bB
C -> c

Теперь, поскольку наша цель состоит в том, чтобы устранить нетерминальные символы (мы уже устранили все посторонние -> lambda производства) мы можем посмотреть на S, B а также C, Мы знаем, что нам нужен начальный символ, поэтому мы могли бы сохранить S как есть. B может только генерировать bB, который содержит нетерминалы; а также bB никогда не может привести к строке только нетерминалов. B является непродуктивным, и мы можем устранить это. Когда мы исключаем непроизводительный символ, любой объединенный термин, в котором он появляется, также должен быть исключен, поскольку каскадное выражение никогда не может получить строку только из нетерминалов (любое каскадное выражение, в котором появляется непродуктивный символ, также непродуктивно):

S -> lambda
C -> c

Применяя наш анализ к Cмы легко видим, что он так же недоступен, как A изначально и так можно устранить таким же образом:

S -> lambda

Эта грамматика в простейших терминах и минимальна в терминах нетерминальных символов и произведений для языка {lambda},