Как найти язык, сгенерированный CFG - PullRequest
1 голос
/ 06 апреля 2011

Если дана контекстно-свободная грамматика, существует ли систематический способ найти сгенерированный язык и выразить его в виде набора, используя описательный , а не аналитический способ, например L (G) = {0 ^ n.1 ^ n | n? = 1} (а не L (G) = {01,0011,000111, ...})?

Я действительно спрашиваю, потому что если дан CFG иВозникает такой вопрос: «Найдите язык грамматики. Подтвердите / обоснуйте свой ответ».тогда как кто-то может доказать / оправдать свой ответ иначе?

1 Ответ

3 голосов
/ 06 апреля 2011

В общем, нет. Например, для произвольной контекстно-свободной грамматики вопрос о том, является ли язык эквивалентным Sigma *, неразрешим - и это самое простое описание КЛЛ можно представить. Еще один неразрешимый вопрос: две контекстно-свободные грамматики A и B определяют один и тот же язык, что не сулит ничего хорошего для более общего вопроса о том, определяют ли грамматику и некоторые другие альтернативные представления один и тот же язык.

В отдельных случаях такие вопросы могут быть решаемыми - к счастью для студентов, изучающих теорию формального языка! Но в свете вышеприведенных результатов о разрешимости вы не найдете простой алгоритм, который переводит вас из грамматики в краткое описание того типа, который обычно представлен в учебниках по теории языка. Это скорее процесс проб и ошибок, где Вы используете некоторую интуицию, чтобы придумать описание кандидата, а затем применить более формальные методы, такие как построение деревьев разбора, или использование свойств замыкания или лемм накачки, чтобы доказать или опровергнуть эквивалентность.

...