Показать язык без контекста

Меня просят показать, что набор песен в форме ABA ^ R не зависит от контекста (где A ^ R - это перевернутое A). Я не знаю, как показать, что язык не зависит от контекста.

Мы специально не изучали, как показать, что язык контекстно-зависимый, поэтому он не может быть слишком сложным. Единственное, о чем я могу думать, - это создать контекстно-свободную грамматику для языка, но я действительно не знаю, достаточно ли этого, чтобы показать, что это контекстно-бесконтекстная грамматика, или как я бы сделал грамматику для набора песен.


computer-science context-free-grammar
person jtht    schedule 26.09.2014    source источник
comment
Здесь есть ответ: stackoverflow.com/questions/3510109/ Также обратите внимание, что создание контекстно-свободной грамматики отлично подходит для демонстрации того, что язык контекстно-свободный.   -  person Spencer Wieczorek    schedule 26.09.2014
comment
Вы не можете использовать лемму о перекачке, чтобы показать, что язык контекстно-зависимый. Его можно использовать только для того, чтобы показать, что это не так. Существуют неконтекстно-свободные языки, удовлетворяющие лемме о накачке.   -  person Nuri Tasdemir    schedule 26.09.2014
comment
Это набор строк A и B или что?   -  person Nuri Tasdemir    schedule 26.09.2014
comment
@NuriTasdemir Да, наверное. Это вся информация, которая у меня есть. Думаю, я попробую сделать для него грамматику.   -  person jtht    schedule 26.09.2014
comment
Используйте 1_. Но что вы имеете в виду под A^R - это A обратное. Можете быть более конкретными   -  person nu11p01n73R    schedule 26.09.2014
comment
Важно знать, что такое A и B в этой формулировке. Если каждый из них представляет собой просто любую строку в заданном алфавите (т.е. один и тот же алфавит для обоих), тогда вам не нужно создавать CFG для языка, вы можете просто рассуждать об этом. (Подсказка: любая строка может быть пустой строкой.)   -  person Michael Dyck    schedule 26.09.2014

Ответы (1)


arrow_upward
0
arrow_downward

Предполагая, что A и B представляют собой набор строк, и они являются контекстно-свободными, тогда существуют контекстно-свободные грамматики для языков A и B, скажем, G_A и G_B. Вы можете легко получить контекстно-свободную грамматику для языка A ^ R из G_A. Просто переверните правую часть правил грамматики, и вуаля у вас есть грамматика для A ^ R.

Если начальная переменная G_A - S_A, G_B - S_B и G_A ^ R - S_A ', то окончательная грамматика будет сочетанием этих грамматик (каждая переменная трех грамматик должна иметь уникальное имя) с новой начальной переменной и новым правило, устанавливающее

S -> S_A S_B S_A'
person Nuri Tasdemir    schedule 26.09.2014
comment
При выводе предложения (песни) из вашего S, S_A 'не ограничивается получением фразы, противоположной тому, что выводится S_A, что, как я думаю, и требуется в исходном вопросе. - person Michael Dyck; 26.09.2014
comment
@MichaelDyck S_A выводит строку из A, а S_A 'выводит строку из A ^ R. Эти две строки не могут быть противоположными друг другу, и это сделано намеренно. Это то, о чем спрашивает ОП. Если они должны быть противоположны друг другу (я так понимаю, вы так думаете), тогда вопрос следует задавать как L = {xyx ^ R | x \ in A И y \ in B} - person Nuri Tasdemir; 26.09.2014