Я в настоящее время изучаю теорию вычислений, где я наткнулся на заявлении, « CFG также может создать регулярный язык» или она должна быть все CFG могут создавать все (любые) регулярные языкContext Free способен генерировать все обычные языки?
Я думаю, что это больше из языковой вопрос, чем вопрос компьютерной науки. Тем не менее, вот что может быть более четкой формулировкой того, что я пытаюсь передать:
Для любого обычного языка существует контекстная грамматика, которая генерирует этот обычный язык.
Для этого мы можем сначала построить каноническую контекстно-свободную грамматику для обычного языка. Мы могли бы взять правильную грамматику в качестве канонического CFG для RL. Я не буду вдаваться в подробности об этой конструкции, но он предполагает, что DFA для языка известен и создает CFG, чьи производственные зеркала переходят в автомат.
Учитывая существование одного CFG для любого RL, мы сразу получаем, что для любого RL существует бесконечно много эквивалентных CFG.
Фактически, REG является подмножеством CF. Таким образом, каждый регулярный язык также не имеет контекста и может быть сгенерирован CFG.