Могут ли быть «мертвые состояния» в грамматике без контекста?

Может ли контекстно-свободная грамматика включать «мертвые состояния» из автомата, такие как

грамм знак равно ({a, б, с}, {A, В, С}, {A \to a В, В \to б, В \to С, С \to с С}, A) ?

$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$

Производственные правила и будут навсегда и никогда не будут генерировать слово. Разрешено ли это или ДОЛЖНЫ ли правила производства заканчиваться терминалом в какой-то момент? $B\to C$ $C\to cC$

context-free automata formal-grammars r3r57
источник

Ответы:

Контекстно-свободные грамматики могут содержать непродуктивные правила . Это принято, потому что каждый CFG генерирует тот же язык, что и некоторый правильный CFG, который не содержит непроизводительных правил, пустых строк и циклов; так что можно с уверенностью предположить, что CFG является правильным без потери общности.

ilke444
источник

Не совсем: надлежащие CFG должны соответствовать еще двум требованиям. Так что я бы переформулировал это.

reinierpost

@reinierpost: Полагаю, вы имеете в виду, что существуют классы CFG, которые запрещают непроизводительные правила, но все же включают в себя неподходящие CFG? Я предполагаю, что переформулировка может быть такой простой, как: «если, например, они не таковы»

mhelvens

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

reinierpost

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

ilke444

Существует ли правильный CFG, который не содержит непроизводительных правил, пустых строк и циклов, генерирующих тот же язык, что и ({a}, {A}, {A-> epsilon}, A)? Мне нравится первое предложение. Возможно, второе предложение должно быть «Это потому, что определение CFG позволяет использовать любую конечную строку терминалов и нетерминалов в качестве левой части производства».

Теодор Норвелл

Да, конечно. Каждый NFA может быть написан как CFG. И создание DFA с «мертвым состоянием» (термин, которому меня учили, это «слив») тривиально.

грамм знак равно ({a}, {A}, {A \to A}, A)

$G = (\{a\}, \{A\}, \{A\to A\},A)$

{a}

$\{a\}$

$\epsilon$

Дэвид
источник