Comments 11
Я давно не получал такого удовольствия от чтения хабрастатьи! Спасибо за действительно понятное изложение и элегантные доказательства. Пишите чаще.
>Он же используется при доказательстве эквивалентности (в некотором не самом простом смысле)
Да просто ссылку дайте на бисимилярность, кому интересно — раскопает. Ну и говорить о КС-грамматиках и не упомянуть pushdown automata как то странно.
В целом неплохая статья, спасибо!
Да просто ссылку дайте на бисимилярность, кому интересно — раскопает. Ну и говорить о КС-грамматиках и не упомянуть pushdown automata как то странно.
В целом неплохая статья, спасибо!
Порождение грамматиками языков можно назвать прямой задачей. Вопрос о способах исследования «черных ящиков» приводит к обратной задаче: пусть у вас есть довольно обширное и представительное множество слов некоторого регулярного или контекстно-свободного языка, каким образом восстановить его грамматику? Пионерская работа в этой теме принадлежит Муру (нужно открыть «Умозрительные эксперименты с последовательностными машинами»), но окончательное решение проблемы или даже точная постановка задачи мне не известна. Может быть кто-нибудь знает о последних достижениях в этой области?
Это известная проблема. Рассматривается в ответвлении машинного обучения под названием Algorithmic Learning Theory. Две постановки:
1. Найти минимальный DFA соответствующий конечному набору позитивных и негативных примеров. Для этой задачи не существует полиномиального алгоритма.
2. Найти минимальный DFA при наличии оракула, который может давать позитивные примеры, а также проверить выученный автомат, а иначе выдать контрпример. Не самая реалистичная постановка. Но здесь существует полиномиальный алгоритм.
Первая проблема называется «Minimum consistent DFA learning problem». Вторую можно погуглить по «Learning Regular Sets from Queries and Counter-Examples» Dana Angluin.
Есть еще один взгляд на проблему: identification in the limit. По сути первый формальный фреймворк машинного обучения. Но там постановка совсем далека от практических задач.
Про совсем свежие результаты сказать к сожалению не могу.
1. Найти минимальный DFA соответствующий конечному набору позитивных и негативных примеров. Для этой задачи не существует полиномиального алгоритма.
2. Найти минимальный DFA при наличии оракула, который может давать позитивные примеры, а также проверить выученный автомат, а иначе выдать контрпример. Не самая реалистичная постановка. Но здесь существует полиномиальный алгоритм.
Первая проблема называется «Minimum consistent DFA learning problem». Вторую можно погуглить по «Learning Regular Sets from Queries and Counter-Examples» Dana Angluin.
Есть еще один взгляд на проблему: identification in the limit. По сути первый формальный фреймворк машинного обучения. Но там постановка совсем далека от практических задач.
Про совсем свежие результаты сказать к сожалению не могу.
Спасибо за Ваш ответ. Мне понравилась идея угадать в пределе. Я ее тоже раньше использовал: моя ранняя статья, которую почему-то удалили с хабра.
Вообще наблюдаемые в символьной последовательности свойства даже образуют топологию. Назовем свойство открытым, если его можно подтвердить на некотором начальном отрезке всякой последовательности, этим свойством обладающей. Например, содержать символ «0» — открытое свойство. Назовем свойство замкнутым, если принадлежность последовательности к нему можно опровергнуть, просмотрев некоторый ее начальный участок, если она им не обладает. Понятно, что отрицание открытого свойства дает всегда замкнутое и наоборот. Проверьте, что выполняются обычные аксиомы топологического пространства: объединение семейства любой мощности открытых свойств и пересечение конечного их числа (последовательность удовлетворяет «объединению», тогда и только тогда, когда удовлетворяет хотя бы одному из них) будет открытым, пересечение семейства любой мощности замкнутых свойств и их конечные объединения — замкнутыми.
Примеры.
Содержать «ноль» — открытое свойство (G-свойство)
Не содержать нулей — замкнутое свойство (F-свойство)
Содержать бесконечно много нулей — свойство класса G_дельта (пересечение счетного числа G-свойств)
Становиться стационарной начиная с некоторого элемента — свойство класса F_сигма (объединение счетного числа F-свойств)
Если речь идет о символах например рациональных чисел, то:
Иметь конечный предел (сходиться) — свойство класса F_сигма_дельта (счетного пересечения (F_сигма)-свойств).
Вообще наблюдаемые в символьной последовательности свойства даже образуют топологию. Назовем свойство открытым, если его можно подтвердить на некотором начальном отрезке всякой последовательности, этим свойством обладающей. Например, содержать символ «0» — открытое свойство. Назовем свойство замкнутым, если принадлежность последовательности к нему можно опровергнуть, просмотрев некоторый ее начальный участок, если она им не обладает. Понятно, что отрицание открытого свойства дает всегда замкнутое и наоборот. Проверьте, что выполняются обычные аксиомы топологического пространства: объединение семейства любой мощности открытых свойств и пересечение конечного их числа (последовательность удовлетворяет «объединению», тогда и только тогда, когда удовлетворяет хотя бы одному из них) будет открытым, пересечение семейства любой мощности замкнутых свойств и их конечные объединения — замкнутыми.
Примеры.
Содержать «ноль» — открытое свойство (G-свойство)
Не содержать нулей — замкнутое свойство (F-свойство)
Содержать бесконечно много нулей — свойство класса G_дельта (пересечение счетного числа G-свойств)
Становиться стационарной начиная с некоторого элемента — свойство класса F_сигма (объединение счетного числа F-свойств)
Если речь идет о символах например рациональных чисел, то:
Иметь конечный предел (сходиться) — свойство класса F_сигма_дельта (счетного пересечения (F_сигма)-свойств).
Для него выполнено утверждение леммы, так что aⁿbⁿcⁿ = uvxyz, причём |vxy| ≤ n и vy ≠ ε.
Значит, строка vxy не является пустой и при этом не содержит либо символ a, либо символ c, ведь эти символы разделяются последовательностью из n символов b.
Из сказанного, кажется, не следует, что vxy ≠ bⁿ. Тогда строка vxy не содержит ни символа a, ни символа c.
В таком случае uvkxykz тоже не принадлежит языку, поскольку тогда число символов b зависит от k и значит может не совпадать с числом символов a и c. Но в строгом доказательстве про это наверное надо упомянуть.
Кстати там ниже по тексту видимо опечатка, написано uvkzykz, должно быть uvkxykz
, но далее выразил эту мысль неаккуратно. Сейчас исправил =)
Sign up to leave a comment.
Леммы о разрастании для регулярных и контекстно-свободных языков