Проверить регулярность языка

[NiGHTeR]

Помогите пожалуйста с задачей, нужно проверить регулярность языка $L$ в алфавите $\{0,1\}$ состоящего из всех слов длины больше 6 таких что последний символ совпадает с символом на 7-й от конца слова позиции.

Если регулярный, то нужно построить конечный автомат, принимающий язык, иначе доказать что такого автомата нет. Ни на какие другие теоремы опираться больше нельзя. Подскажите пожалуйста, не знаю с чего начать

[Joker_vD]

Ну и стройте, в чем загвоздка? Пропустить первые шесть букв, потом пропускать все, пока не встретится буква, бывшая на седьмом месте, на которой слово обрывается.

[Legioner93]

Тарасов Задание 1 № 5(i)?!

[NiGHTeR]

Тарасов, Тарасов)

Цитата:

Ну и стройте, в чем загвоздка? Пропустить первые шесть букв, потом пропускать все, пока не встретится буква, бывшая на седьмом месте, на которой слово обрывается.

так слово то с другого конца поступает, и как вообще реализовать "пропустить все буквы" нам же неизвестно заведомо сколько их и какие они

[Joker_vD]

Так. Ну-ка стойте. Надеюсь, вы согласны, что грамматика

$$(0(0|1)^*0)|(1(0|1)^*1)$$

регулярна? Что существует НКА, ей соответствующий?

[NiGHTeR]

я не знаю что такое грамматика

[Joker_vD]

Опа. Оригинальный у Тарасова подход. Ладно. Тогда постройте для начала три автомата:

1. Распознающий слова длины ровно шесть.
2. Распознающий слова, начинающиеся и заканчивающиеся нулем.
3. Распознающий слова, начинающиеся и заканчивающиеся единицей.

P.S. Грамматика — это средство задания языка. Для регулярных языков в качестве грамматик использует регулярные выражения, которые по природе своей довольно прозрачно переводятся в конечные автоматы.

[NiGHTeR]

все, я думал автомат должен быть детерменированным...

такой пойдет?



зеленый кружок - начальное состояние, красные - конечные состояния

стрелки без букв - переход при любой поступившей букве

где многоточия - пропускаем еще 4 символа

[arseniiv]

Вот автомат, распознающий слова длины ровно четыре (забыл, что надо было 6):



NiGHTeR, какой ужас!

-- Пт сен 09, 2011 16:22:32 --

Начальное состояние самое левое, пометить забыл.

[NiGHTeR]

arseniiv
почему ужас-то?

[arseniiv]

Не потому, что рисунок страшный, а потому, что автомат какой-то слишком многосостоянный (если правильно понял, что там находится вместо многоточий). Зачем так много состояний?

[_hum_]

А так нельзя? Чисто гипотетически, заведем $2^7$ состояний, каждое из которых соответствует возможной комбинациии последних семи прочитанных на данный момент автоматом букв. Тогда распознать - это значит, встретив терминатор строки, перейти в нужное состояние распознавания в зависимости от того, в каком из состояний с "последними $7$ прочитанными буквами" находились.

[NiGHTeR]

arseniiv в сообщении #481828 писал(а):

Не потому, что рисунок страшный, а потому, что автомат какой-то слишком многосостоянный (если правильно понял, что там находится вместо многоточий). Зачем так много состояний?

не знаю, просто так сразу придумалось, а оптимизировать не стал, мне ж всего регулярность проверить...

_hum_
а автомат тогда еще и полный получается?

[_hum_]

Цитата:

_hum_
а автомат тогда еще и полный получается?

Я лишь поверхностно знаком с теорией конечных автоматов и не в курсе, что означает "полнота автомата".