Если дана контекстно-свободная грамматика, существует ли систематический способ узнать сгенерированный язык и выразить его в виде набора, используя описательный, а не аналитический способ, например L(G)={0^ n.1^n|n?=1} (а не L(G)={01,0011,000111,...}) ?
Я на самом деле спрашиваю, потому что если дается CFG и есть вопрос вроде: «Найдите язык грамматики. Докажите/обоснуйте свой ответ». , тогда как кто-то может доказать/обосновать свой ответ иначе?
В общем, нет. Например, для произвольной контекстно-свободной грамматики вопрос о том, эквивалентен ли язык языку Sigma*, неразрешим — и это примерно самое простое описание CFL, которое можно себе представить. Другой неразрешимый вопрос заключается в том, определяют ли две контекстно-свободные грамматики A и B один и тот же язык, что не сулит ничего хорошего для более общего вопроса о том, определяют ли грамматика и какое-либо другое альтернативное представление один и тот же язык.
В конкретных случаях такие вопросы могут быть разрешимы — к счастью для студентов, изучающих формальный язык! Но в свете приведенных выше результатов разрешимости вы не найдете простого алгоритма, который приведет вас от грамматики к краткому описанию, обычно представленному в учебниках по теории языка. Это скорее процесс проб и ошибок, когда вы используете некоторую интуицию, чтобы придумать описание-кандидат, а затем применяете более формальные методы, такие как построение деревьев синтаксического анализа или использование свойств замыкания или накачивание лемм, чтобы доказать или опровергнуть эквивалентность.
