Класс - регулярный язык
Cтраница 1
Класс регулярных языков замкнут относительно операции итерации. [1]
Класс регулярных языков замкнут относительно объединения, пересечения и теоретико-множественной разности. [2]
Класс регулярных языков замкнут относительно операции произведения. [3]
Класс ультраконечных языков строго шире класса регулярных языков. [4]
Прежде всего сравним классы языков сетей Петри к классом La регулярных языков. [5]
 |
Контекстно-свободный язык сети Петри, не являющийся регулярным. [6] |
Одним из простейших и наиболее изученных классов формальных языков является класс регулярных языков. Эти языки порождаются регулярными грамматиками и конечными автоматами и характеризуются регулярными выражениями. [7]
Этот класс строго содержится в классе рекурсивно перечислимых языков, строго включает класс регулярных языков и частично пересекается с классом контекстно свободных языков. [8]
Всякому конечному автомату соответствует язык, а класс всех языков, порождаемых конечными автоматами, называется классом регулярных языков. Конечный автомат определяется своим языком. Если два конечных автомата имеют одинаковые языки, они эквивалентны. [9]
Если каждая продукция в П имеет вид S - S / З или каждая продукция имеет вид S - fiS, где 0 & ( A U V), a S - пустой символ или S e V, то грамматика порождает регулярный язык. Класс регулярных языков является собственным подклассом класса контекстно-свободных языков. Регулярные языки порождаются конечными автоматами и поэтому называются также автоматными языками. [10]
Язык, распознаваемый конечным автоматом ( F. Среди обычно изучаемых классов языков класс регулярных языков является самым узким и математически наиболее простым. [11]
Теперь, когда мы показали, что не все контекстно-свободные языки являются языками сетей Петри и не все языки сетей Петри являются контекстно-свободными, естественно возникает вопрос: что из себя представляет класс языков, являющихся одновременно контекстно-свободными и языками сетей Петри. В настоящее время мы не в состоянии дать полный ответ на этот вопрос, но известна некоторая информация о языках, входящих в пересечение упомянутых классов. Одним подмножеством класса контекстно-свободных языков сетей Петри является класс регулярных языков. [12]
Страницы: 1