Теорема: $%L$% регулярен тогда и только тогда, когда число классов эквивалентности конечно. Используя эту теорему, надо доказать, что если $%L$% состоит из слов, в которых число нулей равно числу единиц, то $%L$% нерегулярен. Уточнения: $%{X^\ast} = {\{ 0,1\} ^\ast}$%, где $%X$% - любое конечное, $%L \subset {X^\ast} = {\{ 0,1\} ^\ast}$% язык=подмножество $$f(w) =\left\{ \begin{array}{\ast{20}{c}} 1&{w \in L}\\ 0&{w \notin L} \end{array}\right.$$ Два слова $%w1$% и $%w2$% - эквивалентные $%\leftrightarrow \forall w \in {X^\ast} = {\{ 0,1\} ^\ast}$% $%w1w$% и $%w2w$% одновременно или принадлежат, или не принадлежат $%L$%.

задан 18 Июн '15 20:23

изменен 18 Июн '15 23:27

falcao's gravatar image


218k2143

Формулировка теоремы звучит неполно: говорится о классах эквивалентности, но не сказано, на каком множестве оно рассматривается, и как оно задаётся. Этот факт можно доказывать разными способами, но если нужно при помощи теоремы, то надо дать точную формулировку.

(18 Июн '15 20:35) falcao

@Яська: я попытался отредактировать текст, чтобы его можно было прочитать, но тут всё вернулось назад.

Надо везде * заменить на команду \ast так как редактор сайта эти символы трактует как выделение жирного шрифта. Также надо заметить, что конечно множество X, а не X со звёздочкой. Функция f, которая определяется в тексте, далее никак не используется.

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

(18 Июн '15 22:59) falcao

Оно вот как используется:если f(w1w)=f(w2w), то эквивалентны и в обратную сторону тоже верно

(18 Июн '15 23:05) Яська

@Яська: Вы ту же мысль выразили словами, то есть функция $%f$% просто не понадобилась.

Сейчас мне понятно, что надо здесь сказать, поэтому я вскоре напишу.

(18 Июн '15 23:28) falcao
10|600 символов нужно символов осталось
0

Утверждение легко следует из известной "леммы о накачке", но здесь её можно не использовать, применяя идею из её доказательства. Рассуждая от противного, рассмотрим конечный детерминированный автомат, задающий регулярный язык $%L$%.

Рассмотрим слово вида $%00...011...1$%, где число нулей и число единиц равно $%n$%, где $%n$% больше количества состояний автомата. Тогда окажется, что при чтении слова и переходе из одного состояния в другое по рёбрам, мы в процессе чтения нулей дважды посетим одно и то же состояние $%q$%. При этом у нас возникает петля (замкнутый путь из $%q$% в $%q$%), которая задаёт слово ненулевой длины из одних нулей. Вставка такого слова меняет баланс нулей и единиц, а языку $%L$% новое слово по-прежнему будет принадлежать, так как оно принимается автоматом. Получается, что автомат не задаёт язык $%L$% -- противоречие.

Эквивалентными здесь будут те слова, при чтении которых из начальной вершины мы попадаем в одну и ту же вершину (состояние). Конечность множества классов эквивалентности фактически и означает конечность множества состояний автомата.

ссылка

отвечен 18 Июн '15 23:37

Мне непонятно, почему мы попадем дважды в одной и то же состояние при чтении нулей. И не является ли частным случаем это доказательство, если мы предполагаем, что n больше числа состояний

(19 Июн '15 0:08) Яська

@Яська: слово из $%L$% так было выбрано, что в его начале имеется больше нулей, чем состояний у автомата. Понятно, что мы каждый раз находимся в какой-то вершине, и если бы они каждый раз получались новые, то их было бы больше $%n$%.

Частным случаем это, конечно, не является: мы вправе рассмотреть любое слово, принадлежащее $%L$%, и проанализировать, что при этом будет.

(19 Июн '15 0:16) falcao

А то есть у нас не в сумме число нулей и единиц равно n, а число нулей n и число единиц n?

(19 Июн '15 0:27) Яська

@Яська: да, конечно. Мы вправе задавать слово любой длины. Нулей n, и единиц тоже n. Если бы имелось в виду другое, я бы написал "в сумме".

(19 Июн '15 0:30) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×613
×10

задан
18 Июн '15 20:23

показан
377 раз

обновлен
19 Июн '15 0:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru