Регулярное выражение 1 и 0

Question

Я получил этот вопрос, который просит меня выяснить "Why is it foolish to write a regular expression for the language that consists of strings of 0's and 1's that are palindromes?" (они читают то же самое вперед и назад).

Часть 2 вопроса говорит, что "using any formal mechanism of your choice, show how it is possible to express the language that consists of strings of 0's and 1's that are palindromes."

Answer 1

Вам необходимо доказать нерегулярность языка, который вы описали. Есть много способов сделать это, но вот ссылка на один метод .

Прокрутите вниз до накачки леммы. Это довольно просто, используя эту технику доказательства.

Подсказка: Если язык может распознавать двоичные палиндромы, он может распознавать 101, 11011, 1110111, ....

Answer 2

Подсказка: на каком языке анализируются регулярные выражения?

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