Во-первых, давайте упростим это и позаботимся об E, просто не используя c на каком-либо языке и сделав E языком (a + b)*. Далее, давайте разберемся с D, сделав его таким же, как E, но с удалением всех строк простой длины больше двух. Мы можем выбрать C как набор всех строк четной длины за {a, b}: (aa + ab + ba + bb)*. Для неконтекстного и нерегулярного языка мы можем выбрать набор палиндромов четной длины для {a, b}: S -> aSa | bSb | e. Наконец, мы можем выбрать в качестве A набор палиндромов четной длины над {a, b}, которые начинаются с простого числа a s.
Мы могли бы попытаться избавиться от D, сделав его объединение C и некоторого языка, включающего только b, затем делая C равным a* и затем пытаясь найти A и B, используя только a ... но у нас могли возникнуть проблемы с поиском контекста. бесплатный нерегулярный язык, включающий только один символ.