Я пытаюсь выяснить, как определить, какой язык распознает КПК, и чувствую, что я близок, но все еще пропускаю. Возьмем, к примеру, следующий КПК. Я могу составить диаграмму переходов, чтобы выяснить, какова моя дельта (переходы), но с этого момента я теряюсь. Это не домашнее задание, а просто пример из книги. Вот проблема и таблица переходов:
Если я правильно читаю обозначения, это выглядит как L*, где L — это язык, который вы получаете, выполняя цикл только один раз. Чтобы обойти цикл, вы видите «с», некоторое количество «а», столько же «б», затем еще одно «с». Итак, L = ca^nb^nc, а язык этого КПК (ca^nb^nc)*.
Естественно, проверьте это и, пожалуйста, скажите мне, если я ошибаюсь. Я также могу лучше объяснить процесс, через который я прошел, чтобы попытаться понять это.
РЕДАКТИРОВАТЬ: Объяснение того, откуда я беру ^nb^n.
Таким образом, стек начинается только с нижнего символа стека Z. Итак, изначально мы находимся в состоянии 1 со стеком Z — (1, Z). Затем мы видим c и переходим в состояние 2, помещая $ в стек; так что мы находимся в (2, $ Z). Предположим, что мы видим n экземпляров a подряд; каждый раз мы будем добавлять в стек новый c и возвращаться в состояние 2. Следовательно, сейчас мы находимся в конфигурации (2, c^n $ Z). Допустим, мы видим экземпляр b. Мы переходим в состояние 3 и удаляем c из стека; наша конфигурация теперь (3, c^(n-1) $ Z). Теперь нам нужно видеть экземпляры b, пока мы не вернем $ на вершину стека; Итак, в состоянии 3 мы можем видеть (n-1) экземпляров b, каждый из которых приведет к извлечению из стека одного экземпляра c. Увидев эти экземпляры b, мы окажемся в конфигурации (3, $ Z). Наконец, мы увидим еще один экземпляр c и, поскольку $ находится на вершине стека, мы можем извлечь его и вернуться в состояние 1 в нашей начальной конфигурации (1, Z).
(a^n)(b^n) возникает из-за того, что мы помещаем в стек столько экземпляров c, сколько видим 'a' в состоянии 2, и удаляем из стека в состояниях 2 и 3 столько же экземпляров c из стека, когда мы видим экземпляры b. Выбор n для представления длины совершенно произволен... он используется только для указания того, что количество экземпляров a и b должно быть одинаковым, если мы можем увидеть $ на вершине стека и перейти обратно к принимающее государство.
