Контекст свободного и регулярного языка с автоматическими автоматами и бесконечными элементами

Question

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

«Пусть L1 является контекстно-свободным языком и L2 является регулярным. Покажите, что существует алгоритм для определения того, имеют ли L1 и L2 бесконечное число общих элементов».

Я не уверен, как это решить. Я не могу понять, что я понял. Я знаю, что обычные языки не допускают двусмысленности, и мне интересно, нужно ли это рассматривать для этой проблемы. Кроме того, если он находится в разделе «Push-Down Automata», я предполагаю, что это может потребовать создания npda или pda. Может кто-нибудь хотя бы направить меня в правильном направлении. Не просите разрешения HW, но для помощи HW!

Answer 1

1. Учитывая КПК A1 для L1 и DFA A2 для L2, построить A3 признающей пересечение L1 и L2, используя декартову конструкцию машины продукта, как если бы между двумя ДКА. Формальное построение немного беспорядочно, но в основном у вас есть новые состояния, которые отслеживают комбинации старых и добавляют изменения переходов/стеков по мере необходимости.

2. Постройте CFG G3 от A3, используя стандартную конструкцию. Опять же, доказательство грязно, и вы в конечном итоге с грязными грамматиками, но это тоже можно сделать.

3. Удалите ненужные переменные, пустые и единичные производные от G3. Если вы привыкли к нормальной форме Чомского (CNF), это в основном аналогичный процесс.

4. Создать граф зависимостей нетерминалов. Если в вашем графике зависимостей есть цикл, язык G3 бесконечен.

5. Поскольку G3 является грамматикой для общих слов между L1 и L2, G3 производит бесконечно много слов, если L1 и L2 имеют бесконечно много общих слов.