Хотя это выражение принимается детерминированной конечной автоматизацией, но если мы применяем лемму о накачке к этому выражению, лемма о накачке не работает, также это выражение имеет конечные состояния, но не останавливается и не работает непрерывно, ребра продолжают создавать петли ч/б состояний, когда i имеет тенденцию к увеличению, а когда стремится к бесконечности, она не должна останавливаться. Таким образом, для этого выражения можно нарисовать DFA, но лемма накачки и TM не работают. Итак, скажите, это обычная грамматика или нет?
Является ли ^ я ^ 2 | i›=1 обычный?
Ответы (1)
На самом деле DFA нельзя нарисовать (по крайней мере, правильный). Вы правы в том, что лемма о накачке дает противоречие, легко накачать i вверх или вниз, чтобы сделать его неквадратным. Если лемма о накачке показывает, что язык не является регулярным, то по определению нет способа нарисовать DFA для представления этого языка.
Набор состояний бесконечен, должно быть одно состояние для принятия a^1, одно для a^2, одно для a^3 и так далее. Затем есть все состояния между этими принимающими... это довольно быстро становится беспорядочным. В любом случае, если лемма о накачке показывает, что язык не является регулярным (при условии, что вы применяете его правильно), то нет DFA (или регулярного выражения) для представления языка.
person
Stuart Douglas
schedule
14.12.2013
Является ли a(aa+aaa)* регулярным выражением для приведенного выше выражения?
- person peeyush.cray; 15.12.2013
Нет, регулярного выражения нет. Например, a(aa+aaa)* принимает aaa, что явно не принято в языке. Вы получаете это, беря aa в круглых скобках и конкатенируя с внешним a. Вы также можете получить ааааа, повторив аа дважды, ааааааа, повторив 3 раза и т. д.
- person Stuart Douglas; 15.12.2013
