B = {1^k y | k >= 1, y in {0, 1}* and y contains at least k 1's }
Является ли этот язык нормальным? Если да, то как вы это доказываете и как бы вы представили это с помощью регулярного выражения в Python?
Это для работы в классе, поэтому, если бы вы могли объяснить причины и процессы, лежащие в основе вашего ответа, это было бы очень признательно.
Ваш язык эквивалентен этому языку:
B' = {1 y | y in {0, 1}* and y contains at least one 1}
Вы можете доказать, что B' является подмножеством B, так как условие в B' такое же, как B, но с k, равным 1.
Доказательство того, что B является подмножеством B', включает в себя доказательство того, что все слова в B, где k >= 1, также принадлежат B', что легко, поскольку мы можем убрать первую 1 во всех словах в B и установить y как остальную часть строка, то y всегда будет содержать хотя бы одну единицу.
Таким образом, мы можем сделать вывод, что B = B'.
Таким образом, наша задача упрощается: нужно убедиться, что первый символ равен 1, а в остальной части строки есть как минимум 1 1.
Регулярное выражение (нотация CS) будет таким:
10*1(0 + 1)*
В обозначениях, используемых распространенными механизмами регулярных выражений:
10*1[01]*
ЦФА:
Здесь q2 — конечное состояние.
"По крайней мере" является ключом к решению этого вопроса. Если слово станет «равным», то история будет другой.
kв конечном числе состояний. Для формального доказательства воспользуемся леммой о накачке. - person starblue schedule 19.02.2013