Определение регулярного языка

a7137928

) какое?
Рассмотрим такую штуку: конечный граф (кон.число ребер и вершин на ребрах написаны буквы. Мы рассматриваем всевозможные конечные пути в графе (начинающиеся и заканчивающиеся где угодно считывая буквы при проходах по ребрам. При этом получится некоторое множество слов.
1) Оно будет регулярным языком?
2) Можно ли такую конструкцию с графом взять за определение рег. языка?
3) Надо ли требовать, чтобы из одной вершины не выходило два ребра с одинаковыми буквами?

UltraLoko

) Регулярный язык := язык заданный некоторым регулярным выражением.
    Регулярные выражения:
  • 0 есть регулярное выражение, оно задает язык без слов.
  • 1 --//--, оно задает язык в котором имеется одно слово, пустое.
  • a --//-- для любой буквы a из алфавита, оно задает язык {a}
  • если E1 и E2 регулярные выражение, задающие языки L1 и L2, то
    1) E1 E2 -- регулярное выражение, задающее язык L = L1 L2 = { w1w2 | w1 <- L1, w2 <- L2 }
    2) E1+E2 --//-- L = L1 \/ L2
  • если E1 регулярное выражение, задающее язык L1, то E1* -- регулярное выражение, задающее язык L, содержащий пустое слово и являющийся минимальным решением уравнения L = L1 L.
    Другими словами L = {w1w2..wk | wi <- L, k<-N}

1) да.
2) нет. Регулярный язык не обязан содержать пустого слова. Он не обязан вместе с каждым своим словом содержать его реверс. Он не обязан с любыми своими словами содержать их произведение. Достаточно зафиксировать в твоем графе начальные(ую) и конечные вершины - получишь обыкновенный конечный автомат, тогда будет ответ "да". Конечные автоматы и регулярные выражения это одно и то же.
3) нет. еще можно на ребрах вместо букв писать слова, в том числе пустые.

a7137928

Во, классно! Тогда еще немного вопросов.
1) В определении рег.языка N - это алфавит; "<-" значит "принадлежит", \/ - объединение; w* - приписывание к слову w любого слова, составленного из букв алфавита. Правильно?
2)
Регулярный язык := язык заданный некоторым регулярным выражением
Одним? Или конечным их числом?
3) То есть, регулярные выражения непосредственно задают слова и задают некоторые операции над ними (конкатенация, объединение, приписывание звездочки)
4)
Он не обязан вместе с каждым своим словом содержать его реверс. Он не обязан с любыми своими словами содержать их произведение.
Погоди, в описанной мною конструкции этого нет. Если реверс - это слово, прочитанное назад, то у меня нет реверсов, потому что граф ориентированный. Кроме того, совершенно не всегда в таком графе вместе с двумя словами будет и их произведение. Для этого необходимо, чтобы, прочитав первое слово, мы могли оказаться в такой вершине, двигаясь из которой можно прочитать второе. Не для любых двух слов такое верно.
5)
Достаточно зафиксировать в твоем графе начальные(ую) и конечные вершины - получишь обыкновенный конечный автомат, тогда будет ответ "да".
А я ведь могу в качестве начальных и конечных зафиксировать любые вершины? Получается как раз то, что я написал...
6) Вообще, меня интересует представление регулярного языка описанным графом. Задача - понять, что же именно я задаю графом, будет ли это произвольный регулярный язык, или я накладываю какое-то ограничение. Получается, что все-таки накладываю, хотя это ограничение не такое, как ты написал (про реверс и произведение слов а вот какое: вместе с каждым словом язык содержит все его подслова. Потому что писать на ребрах слова, а не буквы, у меня нельзя.

IVA030360

)
w* - приписывание к слову
Нет, w* - это e \/ w \/ ww \/ www \/ wwww \/ ...
2)
Одним? Или конечным их числом?
Неважно - есть же операция "\/"
3)
То есть, регулярные выражения непосредственно задают слова и задают некоторые операции над ними (конкатенация, объединение, приписывание звездочки)
В каком это смысле они задают операции? Они описывают набор слов и всё.
4) С ориентированным ближе к автомату, но всё равно начало и конец не фиксированы.
5)
А я ведь могу в качестве начальных и конечных зафиксировать любые вершины? Получается как раз то, что я написал...
Слово "фиксируешь" не для красоты ведь написано - менять эти вершины потом нельзя ведь. Зафиксируешь одни - будет один язык, другие - другой.
6)
а вот какое: вместе с каждым словом язык содержит все его подслова
Вроде похоже на правду.

a7137928

То есть если язык распознается графом таким образом, как я написал, то он будет регулярным, но обратное неверно, и моя конструкция с графом не является эквивалентным определением рег.языка. Жалко...
А можно еще пару примеров рег. выражений и языков, которые они задают? А то все-таки не совсем понятно, как что работает.
И вообще, это ведь наверное в книжках каких-нибудь есть? Я свои старые лекции по дискре глянул, но ничего не нашел.

IVA030360

А можно еще пару примеров рег. выражений и языков, которые они задают? А то все-таки не совсем понятно, как что работает.
Что именно тебе не понятно? Поищи чего-нибудь про регулярные выражения (в perl, php - это то же самое почти).
И вообще, это ведь наверное в книжках каких-нибудь есть? Я свои старые лекции по дискре глянул, но ничего не нашел
Это не из дискры. Есть в теории формальных грамматик - регулярные грамматики. В построении компиляторов встречается в лексическом анализаторе. И в обработке текстов тоже часто применяют регулярные выражения.
Если нужна теория, то вот пара ссылок на то, что на ВМК рассказывают:
методичка по формальным грамматикам
лекции по конструированию компиляторов

a7137928

Спасибо большое, товарищи!
Эти ссылки здорово помогли!
Вообще, у меня была такая проблема. Я делаю доклад по книжке, в которой автор дает несколько определений объекта под названием "софическая система" или "софик". Это некий набор бесконечных в обе стороны последовательностей символов, удовлетворяющий определенным правилам. Он предлагает несколько определений софика и доказывает их эквивалентность.
Перед этими определениями там проскакивает фраза, что "любой софик задает регулярный язык" (то есть, конечные слова, входящие в бесконечные последовательности из софика, образуют рег.язык). Из контекста совершенно невозможно понять, является ли это утверждение эквивалентным определением софика, или это только его свойство. Теперь мне очевидно, что верно второе.
И еще, для проверки пройденного материала.
регулярное выражение
0|e)1*)*
задает все слова, в которых два нуля не идут подряд, плюс пустое слово, а выражение
(01|1) 0|e)1*)*
задает то же самое, но без пустого слова.
Это верно?

IVA030360

регулярное выражение
0|e)1*)*
задает все слова, в которых два нуля не идут подряд, плюс пустое слово, а выражение
Ну если его скорректировать:
0|e)1+)* или 0|e)11*)*
то да, за исключением того, что есть слова, оканчивающиеся на "0", которые под текстовое описание подходят, но в язык не входят.

a7137928

А что такое отдельный +?
0|e)11*)*
Насколько я понял, это выражение задает
(11 011 1111 01111 111111 0111111...)*
То есть, оно не задает слово 0101, например, которое подходит под описание.
Насчет слов, кончающихся на 0: да, упустил. Тогда вроде можно так: (p) | (p)0, где р - одно из рег.выражений выше.

UltraLoko

А что такое отдельный +?
Это "синтаксический сахар" A+ это сокращенная запись для AA*

a7137928

А-а....
Грин: Я понял. Я перепутал 11* и (11)*. Так что все нормально.
Оставить комментарий
Имя или ник:
Комментарий: